Sorting
Insertion Sort Visualiser
Grow a sorted run on the left, inserting one value at a time.
Grow a sorted run on the left, inserting one bar into it at a time.
- Comparisons
- 0
- Writes
- 0
- for scale
- n² = 196
The counter is an exact count for this run; the curve beside it is the shape that count follows as n grows, not a limit on it.
- Being compared
- Being written
- Pivot or smallest so far
- In its final place
- Ruled out
function insertionSort(a) { for (let i = 1; i < a.length; i++) { const value = a[i]; let j = i - 1; while (j >= 0 && a[j] > value) { a[j + 1] = a[j]; j--; } a[j + 1] = value; } return a;}The highlighted line is the one that produced the picture on the left.
What Insertion Sort does
Insertion sort is how most people sort a hand of playing cards without being taught to. Everything to the left of where you are is already in order; take the next value, walk it back through that sorted run until it meets something smaller, and drop it in.
How it works, step by step
- Treat the first value as a sorted run of one.
- Lift the next value out, leaving a gap.
- While the value to the left of the gap is bigger, shift it one place right. The gap moves left.
- Drop the lifted value into the gap. The sorted run is now one longer.
What to watch for
- On nearly-sorted data the inner loop stops after a comparison or two, so the whole sort is close to linear. No other simple sort does that.
- Shifting is not swapping: each value moves once per step, not twice, which is why insertion sort beats bubble sort on identical input.
- On a reversed array every value has to travel the full width of the sorted run, and the counters blow up to the n² worst case.
Cost
| Best case | O(n) — already in order |
|---|---|
| Average | O(n²) |
| Worst case | O(n²) — reversed |
| Extra space | O(1) |
| Stable | Yes |
When to reach for it
For small arrays and for data that is already nearly in order. It is not a toy: the real sort in most standard libraries switches to insertion sort once a partition is small enough, because the constant factors beat quicksort's at that size.