Insertion Sort and the Inversion Count That Predicts Its Runtime

Insertion sort has a quadratic worst case and is still the right inner loop for a large fraction of real sorting work. Both facts come from the same place: the algorithm’s cost is not a function of $n$ alone but of how far the input is from sorted, measured by a single integer that can be computed in advance. Understanding that integer explains when insertion sort wins, why hybrid sorts use it below a threshold, and why the usual “quadratic, therefore bad” summary is misleading.

The shift loop and what it moves

The algorithm keeps a sorted prefix. For each new element, it walks left through the prefix until it finds a key that is not greater, shifting each larger element one slot right on the way. In C:

void insertion_sort(int *a, size_t n)
{
    for (size_t i = 1; i < n; i++) {
        int key = a[i];
        size_t j = i;
        while (j > 0 && a[j - 1] > key) {   /* strict: equal keys stay put */
            a[j] = a[j - 1];
            j--;
        }
        a[j] = key;
    }
}

Each iteration of the inner loop performs exactly one element move and one key comparison. The outer loop runs $n-1$ times regardless of the input. So the total work is $\Theta(n)$ plus one unit per executed inner iteration, and the inner iteration count is the quantity worth naming.

The inversion count is the inner loop count

An inversion is a pair of positions $i < j$ with $a[i] > a[j]$. Call the total number $I$.

Every inner-loop iteration moves one element left across exactly one larger element. Consider the relative order of the two elements involved: before the move, the larger one is to the left of the smaller one, so the pair is an inversion; after the move, the smaller one is to the left, so the pair is no longer an inversion. No other pair’s relative order changes. Each iteration therefore destroys exactly one inversion and creates none.

The sorted array has zero inversions. Insertion sort performs exactly $I$ inner iterations, no more and no fewer. Each of the $n-1$ outer iterations additionally compares the key with the preceding element once, even when that comparison fails, so the total is $n-1 + I$ comparisons and $I$ moves. The running time is therefore $\Theta(n + I)$, and the identity is exact rather than a bound.

The identity gives the familiar cases as specialisations. Reverse-sorted input has $I = n(n-1)/2$, the maximum, giving the quadratic worst case. Already-sorted input has $I = 0$, giving a single linear scan with one comparison per element. Input where every element is at most $k$ positions ahead of its final place has $I \le nk$, giving $\Theta(nk)$, which is linear for constant $k$.

Why the constant is unusually small

For the linear cases, insertion sort is not merely asymptotically linear; it is fast in absolute terms. The inner loop is a compare against the immediately preceding slot, a conditional branch, and a store to an adjacent address. On the sorted case the branch is never taken, so the loop is one load, one compare, one predictable branch per element, and modern branch predictors handle a never-taken branch well. The access pattern walks backwards through a contiguous array, which a prefetcher can follow.

Compare with merge sort, which on any input performs $\Theta(n \log n)$ comparisons plus an allocation and a copy through a second buffer. At $n = 16$ the logarithm is 4, and the merge sort’s per-comparison overhead, its buffer traffic, and its recursion dominate. This is why library sorts switch to insertion sort for small subarrays rather than recursing to size 1, and why the crossover threshold is usually somewhere in the range of 8 to 32 elements rather than at 2.

The threshold is a tuning parameter, not a theorem. It depends on the cost of a comparison relative to a move, on cache line size, and on whether the comparison is inlined. A sort used on large structs with an expensive comparator prefers a larger threshold; one used on machine integers prefers a smaller one.

Binary insertion sort trades comparisons for moves

The linear search for the insertion point can be replaced by a binary search over the sorted prefix, cutting comparisons per element from up to $i$ to about $\log_2 i$. Total comparisons become $\Theta(n \log n)$.

The moves do not improve. Inserting into position $p$ still shifts every element from $p$ to $i-1$ one slot right, and the number of shifts is set by how many elements precede the insertion point, not by the number of comparisons used to find it. On random input that count grows to the same magnitude, so binary insertion sort is $\Theta(n \log n)$ comparisons and $\Theta(n + I)$ moves. On reverse-sorted input it is still quadratic in moves, and the moves are usually the more expensive operation because each one writes memory.

The trade is only worth making when comparisons are far more expensive than moves: comparing long strings, comparing records with a slow user-supplied comparator, or comparing values that require a function call through a pointer. For integers the binary search saves comparisons but adds a second index computation and a conditional per probe, so the linear scan usually wins on the constant factor, and the mispredictions both forms incur on random input do not change that ordering.

Adaptivity as a spectrum

Insertion sort responds to one measure of presortedness. Other algorithms respond to others, and the choice between them is a choice about which measure describes the data.

Measure	Definition	Algorithm that exploits it
Inversions $I$	pairs out of order	insertion sort, $\Theta(n + I)$
Number of runs	maximal ascending segments	natural merge sort, Timsort
Max displacement $k$	$\max_i \lvert i - \text{rank}(a[i]) \rvert$	insertion sort, $\Theta(nk)$
Longest increasing subsequence	length of the LIS	patience sorting, $O(n \log n)$

No comparison sort can be optimal for every measure simultaneously; the measures are not comparable, and a distribution can be easy under one and hard under another. Data with two long ascending runs and nothing else wrong has $I \approx n^2/4$ but only 2 runs. Insertion sort takes quadratic time on it; a natural merge sort merges two runs and finishes in linear time. Conversely, an array built from adjacent transpositions, $[2,1,4,3,6,5,\ldots]$, has only $n/2$ inversions and never moves an element more than one position, yet it needs about $n/2$ ascending runs, so insertion sort is linear on it while a natural merge sort must merge all of those runs.

Stability comes from one comparison operator

The loop condition above uses a[j-1] > key, strictly greater. An element is shifted only when it is strictly larger than the key, so an element equal to the key stays to the left of it, and equal elements keep their original relative order. Replacing > with >= makes the sort unstable and changes nothing else about its cost. The one-character difference is the whole stability guarantee, and it is the reason insertion sort is a safe base case for a stable hybrid sort while an unstable partition step is not.

Where insertion sort is the wrong tool

The exact cost identity cuts both ways. If the input is a random permutation, $I$ has expected value $n(n-1)/4$, so insertion sort performs about $n^2/4$ moves, each a memory write. For $n = 10^6$ that is on the order of $2.5 \times 10^{11}$ writes, which is far beyond any practical time budget. The adaptivity is not a partial mitigation on random input; it is no mitigation at all, because random input is maximally non-adaptive.

Two failure modes deserve naming. First, the quadratic move cost applies even when the comparison count is reduced, so binary insertion sort does not rescue large random inputs. Second, insertion into a sorted prefix of a large array touches a different cache line for every shift once the prefix exceeds the cache, so the effective cost per move rises with $n$ even though the move count is fixed by $I$.

Both are why library sorts use insertion sort as a terminator: it finishes small subarrays left by a divide-and-conquer sort, where $n$ is under a cache line’s worth of elements and the prefix stays in L1. Used that way its quadratic term never dominates, and its adaptivity cleans up the local disorder that partitioning leaves behind. The hybrid that does this deliberately, and bounds its own worst case at the same time, is described in introsort and depth-limited hybrids.