Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Sorting

Insertion Sort Visualiser

Grow a sorted run on the left, inserting one value at a time.

Starting order

Grow a sorted run on the left, inserting one bar into it at a time.

Comparisons
0
Writes
0
for scale
n² = 196
AverageO(n²)extra space O(1)

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

  1. Treat the first value as a sorted run of one.
  2. Lift the next value out, leaving a gap.
  3. While the value to the left of the gap is bigger, shift it one place right. The gap moves left.
  4. 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 caseO(n) — already in order
AverageO(n²)
Worst caseO(n²) — reversed
Extra spaceO(1)
StableYes

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.

Read more