Insertion Sort

Intuition

Insertion sort sorts the array the way most people sort a hand of playing cards. Start with the leftmost card alone — a one-element "sorted hand". Pick up the next card, slide it backwards past every card that's larger, and drop it in its proper place. The sorted hand on the left grows by one each pick. After n − 1 picks the whole array is sorted.

The single concept that makes it click: each pass takes one new value (the key) and inserts it into a region that is already sorted.

How It Works

One outer loop over the array, one inner loop that walks backwards:

• Outer loop runs i from 1 to n − 1. Slot i is the new card being picked up; positions 0..i − 1 are the already-sorted hand.
• Lift the key. Read key = arr[i] and remember it. The slot at arr[i] is now logically empty — its old value lives in key.
• Inner loop runs j from i − 1 down toward 0, but stops as soon as arr[j] <= key. Every iteration shifts arr[j] one slot to the right (arr[j + 1] = arr[j]) — making room for key — and decrements j.
• Place the key. When the inner loop exits, arr[j + 1] is the empty slot where key belongs. Write arr[j + 1] = key.

The key invariant: at the top of each outer iteration, arr[0..i − 1] is sorted. The inner loop preserves that invariant by carving out the correct insertion point.

Step By Step

For the default input [38, 12, 56, 7, 41, 23, 19]:

1. Pass i = 1. key = 12. Sorted hand is [38]. Compare 38 > 12 → shift 38 right. j becomes −1. Place key at index 0 → [12, 38, 56, 7, 41, 23, 19].
2. Pass i = 2. key = 56. 38 < 56 → loop exits immediately. 56 stays where it is.
3. Pass i = 3. key = 7. Shift 56, 38, 12 one slot right in turn until j = −1. Place 7 at index 0 → [7, 12, 38, 56, 41, 23, 19].
4. Pass i = 4. key = 41. 56 > 41 → shift 56. 38 < 41 → stop. Place 41 →[7, 12, 38, 41, 56, 23, 19].
5. Pass i = 5. key = 23. Shift 56, 41, 38 → place at index 2 → [7, 12, 23, 38, 41, 56, 19].
6. Pass i = 6. key = 19. Shift 56, 41, 38, 23 → place at index 2 → [7, 12, 19, 23, 38, 41, 56]. Done.

In the visualization, watch the bar at position i lift out of the row and float above as the key. The cursor j walks left, and each shifted bar slides one slot rightward to fill the gap. When j finds a bar smaller than the key (or runs off the left edge), the floating key drops back into the row at j + 1.

Complexity

Space: O(1) — in place.

Insertion sort is adaptive: the inner loop short-circuits the moment arr[j] <= key. On a nearly-sorted array the inner loop almost never runs, so the total cost approaches O(n). This is why real libraries (Java's Arrays.sort for primitives, Python's Timsort) fall back to insertion sort for short subarrays and final cleanup passes — it's optimal on the inputs the divide-and-conquer phases hand it.

Edge Cases

• Empty or one-element array — outer loop runs zero times.
• Already sorted input — every inner loop exits on the first iteration. One comparison per outer pass → O(n) total. This is the case that makes insertion sort a real choice for "almost sorted" data.
• All equal values — arr[j] > key is always false, inner loop never runs. O(n) total.
• Duplicates — insertion sort is stable because the inner loop uses strict >. An equal value never crosses past another equal value, so original relative order is preserved.

Common Mistakes

• Using >= instead of > in the inner-loop guard. That breaks stability — equal values get shifted past each other unnecessarily.
• Forgetting the off-by-one when placing the key. After the loop, arr[j] is the slot that passed the test (or j = −1). The key belongs at arr[j + 1], not arr[j].
• Overwriting before remembering. Without lifting the value into key first, the very first shift overwrites it. The "key holds the value we're inserting" step is non-optional.
• Shifting one cell too few. Inside the loop, the assignment is arr[j + 1] = arr[j] — the value at j moves up, leaving j conceptually empty for the next iteration to overwrite. Writing arr[j] = arr[j - 1] shifts the wrong direction relative to where the key will land.