Insertion Sort: Growing a Sorted Prefix

The Idea#

Insertion Sort is how almost everyone sorts a hand of playing cards without thinking about it. You pick up cards one at a time and slide each new card into the right spot among the cards you've already arranged. The cards to the left of your current card are always sorted; the cards to the right haven't been touched yet. The algorithm grows a sorted prefix one element at a time, shifting larger neighbors over to make room for each new arrival.

---

How It Works#

The array is mentally split into two regions: a sorted prefix on the left and an unsorted suffix on the right. Each pass picks the next unsorted element (the "key"), and shifts elements of the sorted prefix one slot to the right until the key's correct spot is uncovered. Then the key slides in.

The success-green slots are the sorted prefix, the part of the array you can rely on to be in order. Every pass extends that prefix by exactly one element.

---

The Algorithm#

1. Treat arr[0] as a sorted prefix of length 1.
2. Loop i from 1 to N - 1. The element at arr[i] is the "key".
3. Walk backwards from i - 1, shifting elements one slot to the right while they're greater than the key.
4. When you hit a position whose value is <= key (or you fall off the left edge), drop the key into the gap.
5. The sorted prefix is now one element longer. Continue until i = N - 1.

---

Trace Through an Example#

Running insertion sort on [5, 2, 4, 1, 3]:

Step	Action	Array State
Start	prefix is just [5]	[5, 2, 4, 1, 3]
i = 1	key = 2; shift 5 right, insert 2 at 0	[2, 5, 4, 1, 3]
i = 2	key = 4; shift 5 right, insert 4 at 1	[2, 4, 5, 1, 3]
i = 3	key = 1; shift 5, 4, 2 right, insert 1 at 0	[1, 2, 4, 5, 3]
i = 4	key = 3; shift 5, 4 right, insert 3 at 2	[1, 2, 3, 4, 5]
Done	prefix is the whole array	[1, 2, 3, 4, 5]

You can read the array left-to-right at any moment and the sorted region is always there in front of you.

---

Complexity#

Case	Time	Why
Best	O(N)	already sorted, so the inner while loop never executes
Average	O(N²)	each key shifts roughly N/4 slots on average
Worst	O(N²)	reverse-sorted, so every key shifts the entire prefix
Space	O(1)	in-place, only the key variable

The headline number is the O(N) best case. For nearly-sorted arrays (where every element is at most a few slots from its correct position), insertion sort runs in nearly linear time. This is why it beats fancier O(N log N) sorts on small or nearly-sorted inputs.

---

When Should You Use It?#

• Use it for small arrays (~10-50 elements). The low constant factor and tight inner loop beat merge sort and quick sort below that threshold.
• Use it when data arrives one element at a time and you need an "always sorted" buffer: streaming sensor readings, leaderboards, online algorithms.
• Don't use it as your only sort for general input. On large random arrays, the O(N²) shifts will crush you.
• The transferable pattern: insertion sort is the workhorse inside Tim Sort, the algorithm behind Python's sorted() and Java's Arrays.sort() for objects. Tim Sort uses merge sort for the big picture and insertion sort for small runs, because that combination is genuinely the fastest thing we know on real-world data.

---

Try It#

Let's take the example in the visualization below: [5, 2, 8, 1, 9, 3, 10, 4, 6, 7]. The i chip marks the key being placed; the j chip walks backwards through the prefix, and the decision panel spells out each arr[j] > key verdict before the shift happens.

The thing worth watching is how wildly the cost per key varies:

Key	Shifts needed	Why
8 (i = 2)	0	bigger than everything in [2, 5], placed instantly
1 (i = 3)	3	smaller than everything, walks the whole prefix
9, 10	0 each	arriving already larger than the prefix
4 (i = 7)	4	has to push past 5, 8, 9, 10

Keys that arrive already in order cost nothing at all; keys that arrive far out of place pay for every slot they travel. That single observation is the complexity table above. An already-sorted array is the case where every key costs zero, which is why the best case collapses to O(N).

One difference from the diagram earlier: the visualizer only paints the bars green once the whole array is done, so track the i chip rather than the colour to see where the sorted prefix currently ends.