← Knowledgebase

Insertion sort

The idea

Insertion sort is how many people sort a hand of cards: keep the cards you've already looked at in order, and slide each new card into its place among them.

  1. The first value on its own is a sorted part of length 1.
  2. Take the next value, the key, and hold it aside.
  3. Walk left through the sorted part: while a value is larger than the key, shift it one place right.
  4. When you reach a smaller value (or the front), drop the key into the gap. The sorted part is one longer.

sorted the sorted part so far key the value being inserted ? not looked at yet done all sorted

Cost: it depends on the input

Every shift moves one value past the key, fixing one inversion: a pair of values in the wrong order. So the number of shifts is exactly the number of inversions. A sorted array has none, so insertion sort runs in linear time; a reversed one has the most, n(n − 1)/2.

Insertion sort
Best timeO(n), on input that's already sorted
Worst and average timeO(n²)
Extra spaceO(1): in place
Stable?Yes: a value only moves past larger ones

For small or nearly sorted arrays it beats the O(n log n) sorts, which is why real libraries switch to it for short pieces inside quicksort and merge sort.