Sorting in linear time

◈ 6 cards

Counting sort Θ(n+k) (stable, reverse pass); radix sort Θ(d(n+k)) (LSD, needs a stable inner sort); bucket sort Θ(n) average — how they dodge the lower bound.

Beating the bound by not comparing

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

Counting sort — $Θ (n + k)$

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

Zero a count array $C [0.. k]$ .
Count: for each $A [j]$ , increment $C [A [j]]$ — now $C [i]$ = number of keys equal to $i$ .
Prefix sums: $C [i] + = C [i - 1]$ — now $C [i]$ = number of keys $\leq i$ , i.e. the position of the last copy of value $i$ .
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 $Θ (n + k)$ , which is $Θ (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 — $Θ (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 $Θ (n)$ .

Bucket sort — $Θ (n)$ average

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

Worked example

Counting sort on $⟨ 2, 5, 3, 0, 2, 3, 0, 3 ⟩$ 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 $⟨ 0, 0, 2, 2, 3, 3, 3, 5 ⟩$ . The runnable exercises do this and a stability demo.

C is indexed by *key value*, not by position — that is how counting sort avoids comparing. After the prefix pass, C[3] = 7 says "seven keys are ≤ 3", which is exactly the last slot a 3 may occupy.

Placement runs right to left. A[7] = 3 takes the *last* slot reserved for 3s, so the earlier 3s land before it — equal keys keep their input order, and that stability is what radix sort depends on.

One stable counting sort per digit, least-significant first. After the tens pass the numbers are correctly ordered on their last two digits; the hundreds pass then finishes the job.