Counting, radix and bucket sort each demand a different precondition — what are the three?

### One family, three admission tickets Counting, radix and bucket sort are grouped together because none of them is limited by the Ω(n log n) comparison lower bound. That bound constrains algorithms whose only information about the data comes from asking "is a < b?". All three of these read the key itself — as an index, as a sequence of digits, or as a number to scale into a slot — so the bound simply does not apply to them. That shared escape hatch is where the similarity ends. **Counting sort's ticket: a small, discrete key range.** The algorithm allocates one counter per possible key value, so the key must be usable directly as an index into a table of size `k`. Cost O(n + k), memory O(k). It is superb for grades, priority levels, ages, byte values — anything with tens or thousands of distinct values. It is unusable when `k` is enormous relative to `n`, and it cannot touch continuous keys at all, because there is no such thing as a counter per real number. **Radix sort's ticket: keys that decompose into a bounded number of digits.** Process the keys digit by digit with a stable pass per digit, `d` passes at O(n + k) each for O(d(n + k)) total, where `k` is the size of the digit alphabet rather than of the whole key range. This is what makes it viable where counting sort is not: a 64-bit integer has an astronomically large value range but only eight 8-bit digits. Its requirement is structural — the key must be decomposable, and fixed-width helps enormously — and it makes **no distributional assumption whatsoever**. Skewed input costs the same as uniform input. **Bucket sort's ticket: a benign distribution over a known range.** It scales the key value into one of `k` slots, sorts each slot, and concatenates. Its expected O(n) holds when the keys spread so that each slot stays small. Nothing about the key's *format* guarantees that; the guarantee lives in the *data*. ### The distinction that matters in an interview | Sort | Precondition | Bound | Where the bound comes from | |---|---|---|---| | Counting | Discrete keys over a small range k | O(n + k), deterministic | Key format | | Radix | Keys split into d bounded-width digits | O(d(n + k)), deterministic | Key format | | Bucket | Known range plus a spreading distribution | O(n) expected, O(n²) worst with a quadratic inner sort | Key distribution | Counting and radix let you verify eligibility by reading a schema: are these integers, what is the range, how many digits. Bucket sort's eligibility cannot be read off a type — you have to measure the data, and a measurement can go stale. That is the single sharpest way to state the contrast, and it is why bucket sort is the one of the three that shows up in post-mortems. Two secondary distinctions are worth carrying. **Comparisons**: counting and radix perform none at all, while bucket sort compares inside its buckets — it is a hybrid, not a pure distribution sort. **Composition**: radix sort's per-digit pass is conventionally counting sort, which is why radix inherits the requirement that its inner pass be stable; reorder equal digits and earlier passes' work is destroyed. ### Choosing between them on a real key - Small integer categories, values in the hundreds → counting sort; it is the simplest and the fastest. - Wide integers or fixed-length identifiers → radix sort; the value range stops mattering once you chop it into digits. - Real-valued measurements over a known interval, and you have *measured* the spread → bucket sort, with a fallback for oversized buckets. - Unknown range, unknown shape, mixed or comparable-only keys → a general comparison sort. Its O(n log n) is unconditional, which is a feature. That last line explains something candidates often find surprising: mainstream runtimes do not ship bucket sort as a default. Python and Java default to adaptive stable merge-based sorts, while Rust and C++ ship their own comparison hybrids — four ecosystems, four engineering decisions, all comparison-based. A general-purpose library cannot assume anything about your keys' distribution, so it cannot offer a distribution sort as the default; distribution sorts are something *you* select when *you* can vouch for the data. ### The wrong answer to avoid "They're all linear-time sorts." None of them is unconditionally linear: counting is linear only when `k` is O(n), radix is linear only when `d` is a constant, and bucket is linear only in expectation over a cooperative distribution. Naming the condition attached to each is the whole answer.