Cairn
algorithms · sorting · O(n²)

↩ back to Comparison Sorts

Insertion Sort

Insertion sort builds a sorted array one element at a time, the way most people sort a hand of playing cards: keep a sorted pile in your left hand, and for each new card, slide it in from the right until it's in the right spot relative to the cards already there. The array is split into a sorted prefix (on the left) and an unsorted remainder (on the right). Each pass grows the sorted prefix by exactly one element.

Try it

Enter a comma-separated list of numbers, then step through the sort. Bars in the shaded region are the sorted prefix; the accent-colored bar is the "hole" currently being carried into place.

Press Load, then Step through the sort.

Why it works

The invariant is simple: before each pass, the first i elements of the array are sorted relative to each other (initially i = 1, since a single element is trivially sorted). Each pass takes the next element — the key — out of the unsorted remainder, and shifts sorted elements one slot to the right for as long as they're bigger than the key. When it hits an element that isn't bigger (or runs out of array), it drops the key into the gap that shifting left behind. That gap is the "hole" the demo highlights — it's not a swap, it's a chain of shifts followed by one write.

Reference implementation

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let hole = i;
    while (hole > 0 && arr[hole - 1] > key) {
      arr[hole] = arr[hole - 1]; // shift right
      hole--;
    }
    arr[hole] = key; // drop the key into the gap
  }
  return arr;
}

Pitfalls

It's a shift, not a swap. A common bug is writing this as repeated swaps ([arr[hole], arr[hole-1]] = [arr[hole-1], arr[hole]]) instead of one extracted key plus shifts. Swapping works but does roughly twice the writes — harmless for correctness, worth knowing if you're optimizing.

Measure it instead of taking "roughly twice" on faith. This race runs both versions of the inner loop — the shift-based reference implementation above, and the swap-based variant this Pitfall warns about — over the exact same array, and counts every real write to arr (a shift is one write, a swap is two, plus one final placement write for the shift version only).

Press "Run race" to count real writes for both implementations on the same array.

At n = 5,000, reverse sorted — every pass shifts all the way to the front, the worst case for both versions: the shift version makes exactly 12,502,500 writes (n(n-1)/2 shifts plus one placement per pass), the swap version makes 24,995,000. That's a ratio of 1.9992 — "roughly twice" holds almost exactly. Random input (regenerated on every run, so exact counts vary) lands at essentially the same ratio, around 2.0, because every swap the loop performs still does the shift version's one write plus exactly one extra — the ratio doesn't depend on how many writes happen, only on the fixed cost difference per write. Already sorted is the case that breaks the comparison instead of confirming it: the inner while never fires, so the shift version makes exactly n writes (one placement per pass, zero shifts) while the swap version makes zero — "roughly twice" has nothing to be twice of when there's nothing to shift in the first place.

Quadratic on reverse-sorted input. Every new element has to shift past every element already placed, so a strictly descending array is the worst case: O(n²) comparisons and shifts. An already-sorted array is the best case — the inner while never fires, so it's O(n).

Stability. The condition is arr[hole - 1] > key, strictly greater — equal elements never shift past each other. That makes insertion sort stable: two equal elements keep their original relative order. Change it to >= and it still sorts correctly, but stability breaks.

Complexity

Time: O(n²) worst and average case, O(n) best case (already sorted). Space: O(1) extra — it sorts in place. Despite the quadratic worst case, insertion sort is genuinely useful: it's fast on small or nearly-sorted arrays, and several production sort implementations (including V8's Array.prototype.sort and Timsort) switch to it for small sub-arrays because its low constant-factor overhead beats O(n log n) algorithms once n is small enough.

For a sort that doesn't have that quadratic worst case, see merge sort — it trades insertion sort's O(1) space and adaptive best case for a guaranteed O(n log n) no matter the input. Or, to keep the O(1) space and the same shift-based logic while cutting down how far elements have to travel, see shell sort — it runs this exact algorithm's inner loop at shrinking gaps instead of gap 1 only. See Choosing a Comparison Sort for how all twelve comparison sorts on this site stack up against each other. The 12,502,500 figure above for the n = 5,000 reverse-sorted worst case is also the baseline selection sort's own Pitfalls section measures its swap count against, for the write-count comparison that's the real reason to pick one algorithm over the other when writes are expensive.