programmingconcepts

§ 3.4 · Algorithms

Insertion sort

Grow a sorted section at the front, sliding each new value left until it fits.

Insertion sort builds a sorted section at the front of the list. It takes each next value and shifts larger sorted values one place right until the new value fits, like sorting cards in your hand. It takes O(n²) time on random input but nearly O(n) on almost-sorted data, which is why real libraries use it for small runs.

Average
O(n²)
Best
O(n) when nearly sorted
Extra space
O(1)
Stable
Yes
Requires
ArraysBig O
def insertion_sort(a):
    for i in range(1, len(a)):
        j = i
        while j > 0 and a[j - 1] > a[j]:
            a[j - 1], a[j] = a[j], a[j - 1]
            j -= 1

Press Play or Step to start.

0 comparisons0 swapsstep 0 / 00 / 12 in placecomparingmovingpivot

Fig. 3.4. Blue bars are being compared; orange bars swap as the new value slides left into place.

Intuition

It’s how most people sort a hand of cards. Pick up one card at a time and slide it left past every larger card until it sits in the right spot. The cards in your hand are always in order; only the new card moves.

How it works

  1. Treat the first value as a sorted section of one.
  2. Take the next value. While the value to its left is larger, swap them.
  3. Stop when the left neighbour is smaller or equal, or you reach the front.
  4. The sorted section is now one longer. Repeat until every value is in it.

The figure swaps one step at a time to keep each move visible. Many implementations instead shift the larger values right and drop the new value into the gap, which makes fewer writes.

Complexity

Case Comparisons When it happens
Best n − 1 Already sorted: each value checks one neighbour and stays.
Average about n²/4 Random input.
Worst n(n − 1)/2 Reversed: every value slides all the way to the front.

Like bubble sort, it makes exactly one swap per out-of-order pair. Unlike bubble sort, it stops each slide as soon as the value fits, which is why it is fast on nearly sorted data.

Common mistakes

  1. Comparing with >=. Swapping equal values breaks stability: equal keys change order for no reason.
  2. Starting at index 0. The first value is already a sorted section; the loop starts at 1.
  3. Forgetting the front. The slide must stop at index 0, or it reads a[-1].

When to use it

Small arrays (a few dozen values), data that arrives one item at a time, and input that is already nearly sorted. For large random data it’s O(n²), so use a built-in sort.

Check yourself

Check yourself

The first three values of [2, 5, 7, 3] are sorted. How many comparisons does it take to place the 3?

Check yourself

Which input makes insertion sort do the least work?

Sources

  • Donald Knuth, The Art of Computer Programming, Vol. 3, section 5.2.1.
  • Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, section 2.1, “Insertion sort.”

Newsletter

One new concept each week, by email.

Signup opens soon.