Sorting in linear time

Beating the bound by not comparing

Last lesson: comparison sorts need $\Omega(n\lg n)$. The escape is to stop comparing and exploit structure in the keys — then we sort in linear time.

Counting sort — $\Theta(n+k)$

Assume each key is an integer in $[0,k]$. Counting sort uses values as indices, never comparing two keys. Four phases:

1. Zero a count array $C[0..k]$.
2. Count: for each $A[j]$, increment $C[A[j]]$ — now $C[i]$ = number of keys equal to $i$.
3. Prefix sums: $C[i] \mathrel{+}= C[i-1]$ — now $C[i]$ = number of keys $\le i$, i.e. the position of the *last* copy of value $i$.
4. Place (right to left): for $j = n-1$ down to $0$, put $A[j]$ at $B[\,C[A[j]]-1\,]$ and decrement $C[A[j]]$.

Total $\Theta(n+k)$, which is $\Theta(n)$ when $k=O(n)$. It is stable — equal keys keep their input order — *because* phase 4 runs right-to-left: the last occurrence of a value lands in the rightmost slot for that value.

Radix sort — $\Theta(d(n+k))$

To sort $d$-digit numbers, sort by one digit at a time, least-significant first (LSD), using a stable sort (counting sort) at each pass. Stability is *load-bearing*: each pass must preserve the order the previous (lower) digits established. By induction, after sorting digit $t$ the numbers are correctly ordered on their $t$ least-significant digits. With $d$ constant and $k=O(n)$, radix sort is $\Theta(n)$.

Bucket sort — $\Theta(n)$ average

Assume keys are i.i.d. uniform on $[0,1)$. Scatter $A[i]$ into bucket $\lfloor n\cdot A[i]\rfloor$, insertion-sort each bucket, concatenate. Under the uniform assumption each bucket holds $O(1)$ elements in expectation, giving $\Theta(n)$ average time (worst case $\Theta(n^2)$ if everything clusters into one bucket).

Worked example

Counting sort on $\langle 2,5,3,0,2,3,0,3\rangle$ with $k=5$: the counts are $C=[2,0,2,3,0,1]$, prefix sums make $C=[2,2,4,7,7,8]$, and the right-to-left placement yields $\langle 0,0,2,2,3,3,3,5\rangle$. The runnable exercises do this and a stability demo.