Sorting in Linear Time

The previous lesson proved a wall: any sort that learns only by comparing elements needs $\Omega (n\log n)$ comparisons. That proof has one weakness, and it is our opening here. It assumes the algorithm extracts information one comparison at a time. If instead we treat keys as data we can read, using a key directly as an array index or peeling it apart digit by digit, the decision-tree argument never gets off the ground, and we can sort in linear time.¹ The price is a loss of generality: these algorithms need keys drawn from a small or structured universe, not arbitrary comparables.

Counting sort

Suppose every key is an integer in the range $\left\{0,1,\dots ,k\right\}$. Counting sort never compares two elements. Instead it counts, for each value $v$, how many keys are $\le v$; that count is exactly the final position of the last key equal to $v$. Reading the input back-to-front and decrementing as we place, we drop each element straight into its sorted slot.

The first count loop tallies occurrences; the prefix-sum loop turns counts into ranks (how many keys land at or before each value); the final loop scatters each element into its slot in the output array $B$. Walking the input from $n$ down to $1$ is what makes the sort stable. Equal keys are emitted in their original relative order, because the last such key claims the highest of the slots reserved for that value, and earlier ones fill in below it.

Zooming in on the scatter loop makes the mechanism, and the stability, concrete. Reading $A$ from the back, the last key $A[8]=3$ looks up its rank $C[3]=7$ and drops straight into $B[7]$; we then decrement $C[3]$ to $6$, so the next $3$ we meet (an earlier one in $A$) lands in $B[6]$, just before it, preserving input order.

Analysis. The loops run $\Theta (k)$, $\Theta (n)$, $\Theta (k)$, and $\Theta (n)$ times, so counting sort is $\Theta (n+k)$ in both time and space. As long as $k=O(n)$ this is $\Theta (n)$, genuinely linear, beating the comparison bound because no comparisons happen.² The catch is the space and time in $k$. If the keys range over, say, $32$-bit integers, then $k\approx 4\times 10^9$ dwarfs any realistic $n$, the count array $C$ is enormous, and the method falls apart. Counting sort works best when the key universe is small.

Radix sort

What if the keys are larger, say $d$-digit numbers, so that a single counting pass is infeasible? Radix sort decomposes each key into $d$ digits and sorts one digit at a time. The counterintuitive rule, known since the days of punched-card machines, is to sort by the least significant digit first (LSD), working up to the most significant.

The correctness rests entirely on stability. After sorting on digit $i$, suppose the array is correctly ordered by the low-order digits $\mathrm{1..}i$. Now sort on digit $i+1$ with a stable sort. Two keys differing in digit $i+1$ are ordered correctly by that pass. Two keys agreeing in digit $i+1$ are left in their incoming order by stability, and that incoming order was already correct on digits $\mathrm{1..}i$. So after the pass the array is correctly ordered on digits $\mathrm{1..}i+1$. By induction, after all $d$ passes the array is fully sorted.³ Using an unstable per-digit sort would destroy the work of every earlier pass. This is why the inner sort must be stable, and counting sort is the natural choice.

Zooming in on a single pass shows why stability is not optional. Suppose the array is already ordered on the low digit, and we now sort on the next one. Keys that tie on the new digit must keep their incoming order, since that order already encodes the lower digit; only keys that differ on the new digit may be reordered.

Analysis. With counting sort on each of $d$ digits, each drawn from a range of size $k$, every pass costs $\Theta (n+k)$, for a total of

When $d$ is a constant and $k=O(n)$, for example fixed-width integers split into a constant number of digits in a base of size $\Theta (n)$, radix sort runs in $\Theta (n)$. Choosing the digit size is an engineering tradeoff: larger digits mean fewer passes ($d$ shrinks) but a larger $k$ per pass. For $b$-bit keys, the best choice is typically digits of about ${\log }_{2}n$ bits, so $k\approx n$ and $d\approx b/{\log }_{2}n$.

Bucket sort

Counting and radix sort exploit integer keys. Bucket sort instead exploits a distributional assumption: that the keys are drawn (roughly) uniformly at random from an interval, say $[0,1)$. It scatters the $n$ keys into $n$ equal sub-intervals, the buckets, sorts each bucket with a simple sort like insertion sort, then concatenates the buckets in order.

Scattering is $\Theta (n)$, and concatenation is $\Theta (n)$. The only variable cost is sorting the buckets. If the input is spread uniformly, each bucket holds about one element on average, so the insertion sorts cost $O(1)$ each in expectation.⁴

Analysis. Let $n_i=|B[i]|$. Insertion sort on bucket $i$ costs $O(n_i^2)$, so the expected total bucket-sorting cost is ${\sum }_i\mathbb{E}[O(n_i^2)]={\sum }_{i}O(\mathbb{E}[n_i^2])$. Each key lands in bucket $i$ independently with probability $1/n$, so $n_i$ is Binomial$(n,1/n)$, which has

Summing over the $n$ buckets gives ${\sum }_{i}O(\mathbb{E}[n_i^2])=O(n)$, so the total expected running time is

This is an average-case result: it assumes the inputs are uniformly distributed. Adversarial input, with every key landing in the same bucket, degrades bucket sort to the $\Theta (n^2)$ of a single insertion sort. Bucket sort is the right tool when you know your data is spread evenly (or can cheaply map it so), as with fractional parts of well-mixed values.

Choosing among them

None of these linear-time sorts is a drop-in replacement for a comparison sort like mergesort or heapsort. Each rests on a structural assumption about the keys, so the choice comes down to matching the algorithm to what you know about your data.⁵

Practical guidance:

• Reach for counting sort when keys are integers over a range comparable to $n$ (grades, small ages, byte values). It is also the standard stable subsort inside radix sort.
• Reach for radix sort for fixed-width keys with a larger range, such as $32$- or $64$-bit integers or fixed-length strings, where a single counting pass would need an impossibly large count array.
• Reach for bucket sort when keys are real numbers you believe are uniformly (or near-uniformly) distributed, and you want linear expected time.

And remember the boundary: these methods beat $\Omega (n\log n)$ precisely because they are not comparison sorts. They never ask is $a_i<a_j$?; they compute with the keys. Hand any of them arbitrary comparable objects with no exploitable integer or distributional structure, and the linear-time guarantee is gone, leaving you back at a comparison sort and its $n\log n$ floor.

Takeaways

• The $\Omega (n\log n)$ bound binds only comparison sorts; using keys as array indices or digit sequences sidesteps it entirely.
• Counting sort ranks keys by prefix-summing their counts: $\Theta (n+k)$, stable, linear when $k=O(n)$ but ruinous when $k$ is large.
• Radix sort stably sorts digit by digit, least significant first; stability is what preserves earlier passes, giving $\Theta (d(n+k))$.
• Bucket sort scatters uniform keys into $n$ buckets and sorts each; expected $\Theta (n)$, but $\Theta (n^2)$ if the distribution is adversarial.
• Each linear sort trades generality for a structural assumption on the keys, so choose by what you actually know about your data.