Radix sort never compares two keys, so why doesn't the Omega(n log n) comparison lower bound apply to it?

## What the lower bound actually claims The famous `Omega(n log n)` result is not a statement about sorting in general. It is a statement about **comparison sorts**: algorithms whose only way of gaining information about the input is to ask, of two elements, "does this one come before that one?" Everything else the algorithm does — moving records, allocating buffers, recursing — is free in this model. Model such an algorithm as a **decision tree**. Each internal node is one comparison with two outcomes, so the tree is binary. Each leaf is a final permutation the algorithm can emit. To be correct, the algorithm must be able to emit any of the `n!` orderings of `n` distinct inputs, so the tree needs at least `n!` leaves. A binary tree of height `h` has at most `2^h` leaves, so `2^h >= n!`, hence `h >= log2(n!)`. By Stirling's approximation `log2(n!) = Theta(n log n)`. The height is the worst-case number of comparisons, so **every** comparison sort makes `Omega(n log n)` comparisons in the worst case (and, by a similar counting argument, on average too). The information-theoretic reading is more intuitive: there are `n!` possible answers, so you need about `log2(n!)` bits of information to pin one down, and a yes/no comparison yields at most one bit. `n log n` is the number of one-bit questions required. ## Where radix sort steps out of the model Radix sort never performs the operation the bound counts. In least-significant-digit (LSD) form it makes `d` passes; in pass `p` it looks at digit `p` of each key and distributes the records into `k` buckets, then concatenates the buckets in digit order. Deciding which bucket a record goes to costs a digit extraction, not a comparison against another record. In information terms, one comparison buys at most one bit about the ordering; reading a base-`k` digit buys up to `log2(k)` bits, and reading it for all `n` records costs one linear sweep. That is why the accounting behind the decision tree simply does not describe what radix sort is doing. The same is true of the other non-comparison sorts — they all exploit structure inside the key rather than pairwise order queries. ## What radix sort pays instead Stepping outside the model is not free; the bound is traded for preconditions: - **Keys must be decomposable.** There must be a way to write each key as a fixed sequence of digits over a finite, ordered alphabet, such that comparing the digit sequences lexicographically gives exactly the order you want. Fixed-width numeric identifiers and fixed-length codes qualify; an arbitrary user-supplied ordering rule with no digit encoding does not. - **Cost moves from comparisons to passes.** The bound becomes `O(d(n+k))`: `d` sweeps over all `n` records, each also touching a `k`-entry counting structure. The lens that matters in practice is memory traffic and pass count, not comparison count. - **Space.** The standard formulation writes each pass into an auxiliary array the size of the input, so peak memory is roughly double. - **Stability inside each pass** is mandatory for LSD, because that is what carries earlier passes' work forward. ## The direction of the claim matters "Not a comparison sort" does **not** mean "always faster". Two precise statements: 1. For a **fixed** key width — say identifiers that are always the same number of characters — `d` is a constant set by the format, so `O(d(n+k))` really is linear in `n`. This is the honest case where radix sort beats an `n log n` sort asymptotically. 2. If keys must remain **distinct** as `n` grows, the key width itself must grow: `n` distinct keys need at least `log_k(n)` digits, so `d` is not a constant and the product quietly returns to `n log n` divided by `log2(k)`. Both statements are true simultaneously; which one applies depends on whether the key format is fixed by the problem. A candidate who says "radix sort proves the lower bound is wrong" has the relationship backwards. The bound is a theorem about a restricted machine, and radix sort is a different machine. ## What a good answer sounds like Name the decision-tree argument, say explicitly that it counts comparisons and only comparisons, then say what radix sort does instead (digit extraction and distribution) and what it demands in return (digit-decomposable keys, `d` passes, extra space). That answer shows you understand the bound is conditional rather than universal — which is the whole reason interviewers raise non-comparison sorts.