Insertion Sort Average Case – Comparisons, Shifts and Θ(n²)

Insertion sort builds a sorted prefix one element at a time. Element $i$ is compared with the elements to its left, scanning right to left, and the larger ones are shifted one place to the right until the right spot is found:

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:   # one comparison per loop test with j >= 0
            a[j + 1] = a[j]            # one shift
            j -= 1
        a[j + 1] = key

“Average case” means the expected cost when the input is a uniformly random permutation of $n$ distinct keys.

Shifts: count the inversions

An inversion is a pair $(i, j)$ with $i < j$ but $a_i > a_j$. Each shift fixes exactly one inversion and creates no new ones, so

$$\text{shifts} = \text{number of inversions}.$$

Each of the $\binom{n}{2}$ pairs is inverted with probability $\tfrac12$ in a random permutation. By linearity of expectation,

$$\mathbb{E}[\text{shifts}] = \frac12 \binom{n}{2} = \frac{n(n-1)}{4}.$$

Comparisons: exact expectation

When the element at position $i$ (counting from 1) is inserted, the sorted prefix has $i - 1$ elements, and the new key’s rank among the first $i$ is uniform. Say it moves past $k$ larger elements, where $k \in \{0, 1, \dots, i-1\}$, each with probability $1/i$.

• If $k < i - 1$, the loop makes $k$ successful comparisons plus one failing one: $k + 1$ comparisons.
• If $k = i - 1$ (the key is the new minimum), the loop stops because $j$ reaches $-1$, after $i - 1$ comparisons.

So the expected number of comparisons for this insertion is

$$\frac1i\left(\sum_{k=0}^{i-2} (k+1) + (i-1)\right) = \frac{i-1}{2} + \frac{i-1}{i} = \frac{i+1}{2} - \frac1i.$$

Summing over $i = 2, \dots, n$:

$$\mathbb{E}[\text{comparisons}] = \sum_{i=2}^{n}\left(\frac{i+1}{2} - \frac1i\right) = \frac{n^2 + 3n}{4} - H_n,$$

where $H_n = 1 + \tfrac12 + \dots + \tfrac1n \approx \ln n$. Equivalently, this is $\dfrac{n(n-1)}{4} + n - H_n$: one comparison per inversion, plus about one extra comparison per insertion.

Check, $n = 3$: the formula gives $\tfrac{18}{4} - \tfrac{11}{6} = \tfrac{8}{3} \approx 2.67$. By hand, the second element always costs 1 comparison, and the third costs $\tfrac{4}{2} - \tfrac13 = \tfrac53$ on average, for a total of $\tfrac83$.

Best, average and worst case

Case	Input	Comparisons	Shifts
Best	already sorted	$n - 1$	$0$
Average	random permutation	$\frac{n^2+3n}{4} - H_n \sim \frac{n^2}{4}$	$\frac{n(n-1)}{4}$
Worst	reverse sorted	$\frac{n(n-1)}{2}$	$\frac{n(n-1)}{2}$

So the average case is $\Theta(n^2)$, with a constant about half that of the worst case.

Why insertion sort is still used

• On nearly sorted data its running time is $\Theta(n + I)$, where $I$ is the number of inversions, which can be close to linear.
• It is stable, in place, and has very low overhead. Hybrid sorts such as Timsort and introsort switch to insertion sort for small subarrays (typically 16 to 64 elements).
• Binary insertion sort cuts comparisons to $O(n \log n)$, but the shifts remain $\Theta(n^2)$ on average.

Common mistakes

• Saying the average case is "$n^2/2$". That is the worst case. The average is half of that.
• Equating comparisons and shifts. They differ by about $n - H_n$, which matters for small $n$.
• Assuming duplicates don’t matter. The analysis above assumes distinct keys. With many equal keys there are fewer inversions.