Insertion Sort grows a sorted prefix on the left. For each new element (the key), it shifts larger sorted elements one step right until the key slots into place.

Think of sorting a hand of cards: look at the next card, decide where it belongs among the ones you hold, and slide it in by pushing the larger cards right.

How It Works

1. Treat the first element (index 0) as a sorted prefix of size 1.
2. Take the next unsorted element as the key.
3. Walk backward through the sorted prefix, shifting each element that is larger than the key one position to the right.
4. Insert the key into the vacated position.
5. Advance to the next element and repeat until every element has been inserted.

Key Insight

Insertion Sort is adaptive: if each key only travels a tiny distance, the work stays small. On an already (or nearly) sorted array, each element shifts at most once or twice — a linear O(n) best case.

That is why production hybrid sorts — Timsort (Python/Java) and Introsort — fall back to Insertion Sort for small or nearly-sorted runs. It is also stable, because shifting never makes equal elements cross.

Worked Example

Sort [5, 3, 8, 1, 2] with Insertion Sort:

• Prefix [5], key = 3 → shift 5 right, insert → [3, 5, 8, 1, 2]
• Prefix [3, 5], key = 8 → nothing shifts, insert at end → [3, 5, 8, 1, 2]
• Prefix [3, 5, 8], key = 1 → shift 8, 5, 3, insert at front → [1, 3, 5, 8, 2]
• Prefix [1, 3, 5, 8], key = 2 → shift 8, 5, 3, insert after 1 → [1, 2, 3, 5, 8]

Result: [1, 2, 3, 5, 8]. In the visualizer, the “held” key stays visible (floating above its column) while the larger elements shift right — exactly the mental model above.

Edge Cases & Pitfalls

• Already sorted input — every key is already in place: one comparison each, total O(n).
• Reverse sorted input — each key shifts across the whole prefix: worst case O(n²).
• Duplicates — only shifts on strict > comparisons, so equal keys never cross: stable.
• Nearly sorted with a few outliers — each outlier only travels as far as needed. This is the real-world case it was designed for.

Comparison With Other Sorts

Applications

• Base case inside Timsort and Introsort (the fastest general-purpose sorts)
• Online sorting — maintaining a sorted list as new items stream in one at a time
• Sorting very small collections where recursion and auxiliary buffers cost more than they save

Practice Trajectory

1. Hand-trace Insertion Sort on [4, 2, 7, 1, 3], drawing the sorted prefix after each insertion.
2. Explain why shifting (not swapping) keeps the algorithm stable.
3. Count the comparisons for an already-sorted array of size 5 and confirm it is O(n).
4. Describe how Insertion Sort behaves as the base case of Timsort.
5. Implement it, and verify the array is unchanged (not copied) between steps.