Insertion sort

Sort the way you sort a hand of cards: take the next one and slide it left until it sits in order. Watch each value find its place.

⋯11void insertion_sort(int *a, int n)12{13    for (int i = 1; i < n; i++) {14        int x = a[i];15        int j = i - 1;16        while (j >= 0) {17            comparisons++;18            if (a[j] <= x)19                break;20            a[j + 1] = a[j];21            moves++;22            j--;23        }24        a[j + 1] = x;25    }26}

A sorted prefix that grows

Keep the front of the array sorted. At the start, cell 0 alone is a sorted prefix. Take the value in the next cell, call it x, and compare it with the values of the prefix from the right. Each one larger than x slides one cell right. When a value no larger than x appears, or the front is reached, x goes into the gap that is left. The prefix is now one value longer, and still sorted.

The values slide; nothing is swapped. A swap would write two cells each time a value moves past another. Here each larger value is written once, one cell to the right, and x is written once at the end.

The code and its cost

void insertion_sort(int *a, int n)
{
    for (int i = 1; i < n; i++) {
        int x = a[i];
        int j = i - 1;
        while (j >= 0) {
            comparisons++;
            if (a[j] <= x)
                break;
            a[j + 1] = a[j];
            moves++;
            j--;
        }
        a[j + 1] = x;
    }
}

The invariant: at the top of the outer loop, a[0] to a[i − 1] are sorted. x keeps a[i], so its cell can be overwritten. j walks left through the prefix; each larger value moves to a[j + 1]. When the loop stops, a[j + 1] is the gap, and x goes there.

Counting the work

Each move removes one inversion: x and the value it passes were a pair in the wrong order. So the moves are exactly the inversions, 20 on the house array. Each comparison either leads to a move, or is the last one, against a value no larger than x. That last comparison happens for every value except those that slide all the way to the front, which stop because j runs out. In the house array 2 and 1 reach the front, so 7 of the 9 values make one extra comparison: 20 + 7 = 27. insertion.c prints 27 comparisons, 20 moves.

• Sorted input: every value stops at its first comparison: n − 1 comparisons, no moves.
• Reversed input: every value slides to the front: n(n − 1)/2 comparisons and as many moves, 45 and 45 for ten.
• Random input: on average half the pairs are inversions, about n²/4 moves and comparisons.

The control above runs all three. The nearly sorted order 1 2 4 3 5 6 8 7 9 10 has 2 inversions: 2 moves, and 9 + 2 = 11 comparisons.

Properties

Insertion sort is in place (one x and one j), stable (a[j] <= x stops before an equal value, so x never passes it) and adaptive: its cost is n − 1 plus the number of inversions, so nearly sorted input costs almost nothing. Against bubble sort on the same house array it makes 27 comparisons instead of 39, and 20 single-cell moves (plus 9 placements of x) instead of 20 swaps of two cells each.

A list, sorted the same way

On a linked list, a value need not slide: it can be unlinked and linked in at its place, two pointers changed. insertion-list.c takes each node off the front of the input list and walks a pointer to a link along the sorted list, as Removing from a linked list did:

struct node **link = &sorted;
while (*link != NULL && (*link)->key <= n->key)
    link = &(*link)->next;
n->next = *link;
*link = n;

It prints 1 2 3 4 5 6 7 8 9 10. The comparisons are the same kind of walk, but from the front of the sorted list, and no value moves in memory.

Worked example

Inserting 1 into 2 6 9. 1 is compared with 9, 6 and 2; each is larger and slides right, and 1 reaches the front: 3 comparisons, 3 moves. Sorting all of 2 6 9 1 adds one comparison each for 6 and 9: insertion-extra.c prints 5 comparisons, 3 moves.

A thousand scrambled values. For 1,000 values the estimate n²/4 is 250,000. insertion-extra.c sorts the 1,000 values (i × 389) mod 1009 and counts 251,837 comparisons and 250,838 moves.

Two checks. How many comparisons for 100 values already sorted? (99.) How many moves for 2 1 4 3? (2.)

Where it’s used

Small arrays. For a few dozen values its small, simple loop beats the sorts that are faster on large inputs.

Finishing other sorts. Library implementations of quicksort and merge sort often stop splitting at small ranges and let insertion sort finish them, since by then the values are nearly in place.

Keeping a list sorted as items arrive. Each new item is one insertion into what is already sorted.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.