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.
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.
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.
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;
}
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).
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.
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.