Counting Sort and Radix Sort

When elements have small integer keys, you can sort them in $O(n)$ time without comparisons. These linear sorts beat the $\Omega(n \log n)$ comparison-sort lower bound by exploiting key structure.

Counting sort

Given $n$ integers in range $[0, k)$:

1. Allocate a count array of length $k$. 2. Make one pass over the input, incrementing counts. 3. Compute prefix sums of the count array (turning counts into starting positions). 4. Make a second pass over the input, placing each element at its position and advancing.

Time: $O(n + k)$. Space: $O(n + k)$ for the output and count arrays. Stable.

When counting sort wins

$k$ is small relative to $n$. Sorting RGB byte values ($k = 256$). Sorting ages ($k \approx 120$). Sorting exam scores in a class ($k = 100$). Linear time, no comparisons, very cache-friendly.

When it loses

$k$ is large. Sorting 32-bit integers ($k = 2^{32}$) directly with counting sort allocates 16 GB. Sorting floats — counting sort doesn't apply.

Radix sort

Sort by one digit at a time, using a stable inner sort (usually counting sort). For 32-bit integers, do 4 passes of 1 byte each. Total time: $O(d \cdot (n + b))$ where $d$ is the number of digits/bytes and $b$ is the base.

For $n = 10^6$ random 32-bit integers, that's about $4 \times 10^6$ work plus $4 \times 256$ count-array overhead. Radix sort beats quicksort on uniform integer data by a real margin.

Bucket sort

Partition the value range into $n$ buckets; insert each value into its bucket; sort each bucket and concatenate. $O(n)$ expected when values are uniformly distributed. Used in floating-point sorting and in massively-parallel sorting systems.