Insertion sort
Keep the left part sorted. Take the next item and slide it left until the one before it is smaller. It is how most people sort a hand of cards.
53819274
Press play or step forward to start.
1function insertionSort(a) {2 for (let i = 1; i < a.length; i++) {3 let j = i;4 while (j > 0 && a[j] < a[j - 1]) {5 swap(a, j, j - 1);6 j--;7 }8 }9}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n | already sorted: one compare per item |
| average | n² | random input |
| worst | n² | reversed input: every item walks to the front |
| space | 1 | sorts in place |
Where it breaks
- Large random input. Each item can walk all the way left, so work grows as n². Pick Reversed above: 28 compares for 8 items.
- But not on nearly sorted data. Pick Nearly sorted: each item only moves a step or two, so it finishes in close to n compares. That is why real libraries switch to insertion sort for small or almost-sorted ranges.
- Equal keys stay in order. It only swaps when strictly smaller, so equal items never jump past each other. That makes it stable.