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.
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 ten
comparison sorts on this site stack up against each other.