Sorting

Insertion Sort

Build a sorted prefix one element at a time, sliding each new value back into its place — the way most people sort a hand of cards.

Green is the sorted prefix — the invariant. Blue is the value being compared. Orange is the element being inserted.

What you're seeing

Each bar is a number; taller is larger. Insertion sort walks left to right, and at every moment the bars on the left form an already-sorted run. It picks the next bar, then slides it leftward past every larger value until it drops into the one spot where it belongs. Watch the green region grow by exactly one bar each round.

It is the algorithm your hands already know: to sort a dealt hand of cards, you keep the cards so far in order and tuck each new card into place.

The rule

insertion_sort(a):
    for i = 1 .. n-1:
        key = a[i]            # the card to place
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j+1] = a[j]     # shift bigger values right
            j = j - 1
        a[j+1] = key          # drop key into the hole

Only two operations matter, and the visualization counts both: a comparison (a[j] > key) and a shift (a[j+1] = a[j]).

The invariant

The reason insertion sort is correct fits in one line: the prefix a[0..i) is always sorted at the top of each round. It holds before the first round (a single element, a[0..1), is trivially in order). Each round preserves it: we open a hole by shifting larger values right, then drop key into the hole, leaving a[0..i+1) sorted. When the loop ends, i = n, so a[0..n) — the whole array — is sorted. That is the entire proof: establish the invariant, show each step maintains it, read off the result at termination.

The cost

BestAverageWorst Comparisonsn−1Θ(n²)Θ(n²) TimeΘ(n)Θ(n²)Θ(n²) SpaceO(1)O(1)O(1)

Set the input to Already sorted and the inner loop never shifts — one comparison per element, a clean Θ(n) pass. Set it to Reversed and every new element must travel all the way to the front: 1 + 2 + … + (n−1) = n(n−1)/2 shifts, the worst case. The counters under the canvas make the gap concrete. Insertion sort is also stable (equal values keep their order) and in-place (O(1) extra space).

In the wild

Insertion sort looks slow, and asymptotically it is — yet it is quietly everywhere, because for small or nearly-sorted inputs its low overhead and cache-friendliness beat the fancy algorithms. Production sorts are hybrids that fall back to it: Timsort (Python's sorted, Java's Arrays.sort for objects) builds its initial runs with insertion sort, and introsort (many C++ std::sort implementations) switches to insertion sort once a partition drops below ~16 elements. So the textbook "toy" sort runs billions of times a day — as the inner gear of the sorts you actually call.

Try this

Switch Initial order to Reversed and watch the comparison counter explode — then to Nearly sorted and see it collapse back toward linear. That spread between best and worst case is the whole personality of insertion sort.

References

  1. Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §2.1 — insertion sort and the loop-invariant proof method. MIT Press, 2022.
  2. Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching, §5.2.1 (Sorting by Insertion). Addison-Wesley.
  3. Sedgewick & Wayne. Algorithms, 4th ed., §2.1. Booksite: algs4.cs.princeton.edu/21elementary.
  4. Peters, T. Timsort description, CPython listsort.txt: github.com/python/cpython · Objects/listsort.txt.