Insertion Sort: Algorithm
What you'll learn: How insertion sort builds a sorted result one element at a time by inserting each new element into its correct position.
The Core Idea
Insertion sort works like organizing playing cards in your hand. You pick up one card at a time and insert it into its proper position among the cards you've already sorted. The left portion of your hand stays sorted, and you grow it by one card with each step.
The algorithm divides the array into two parts: a sorted portion (initially just the first element) and an unsorted portion (everything else). It takes the first element from the unsorted portion and slides it leftward through the sorted portion until it finds its correct spot.
How It Works
- Start with the second element (index 1)—consider the first element already "sorted"
- Compare this element with elements in the sorted portion, moving right-to-left
- Shift larger elements one position to the right to make room
- Insert the element into the gap created
- Move to the next unsorted element and repeat
Example walkthrough:
Array: [5, 2, 4, 6, 1]
Pass 1: Insert 2 into sorted [5]
→ [2, 5, 4, 6, 1]
Pass 2: Insert 4 into sorted [2, 5]
→ [2, 4, 5, 6, 1]
Pass 3: Insert 6 into sorted [2, 4, 5]
→ [2, 4, 5, 6, 1] (already in place)
Pass 4: Insert 1 into sorted [2, 4, 5, 6]
→ [1, 2, 4, 5, 6]
Each pass maintains the invariant that everything before the current position is sorted.
Key Takeaway: Insertion sort grows a sorted region by repeatedly taking the next unsorted element and inserting it into its correct position among the already-sorted elements, much like sorting cards in your hand.