How do you choose an LSD radix sort's digit width when sorting 100 million fixed-length order codes?
answer
- there is really only one knob
- passes shrink, buckets grow
- ceil(w over b) versus two to the b
- where does the bucket array live?
- cache residency beats the formula's optimum
basics
~20 sTrade passes against bucket memory: a digit of b bits gives ceil(w/b) passes and 2^b buckets. Widen it until the bucket array stops fitting in fast cache — in practice 8 to 16 bits — then measure.
solid answer
~50 sThe cost model is `d * (n + k)` with `d = ceil(w/b)` passes and `k = 2^b` buckets. At 100 million 12-symbol codes, a digit of one symbol means 12 passes with a few hundred buckets; packing two symbols into a 16-bit digit means 6 passes with 65,536 buckets. Each pass is a full scatter over 100 million records, so halving the pass count roughly halves the dominant memory traffic — while the bucket array, at a quarter megabyte, still sits in cache. Push the digit to 20 or 24 bits and the bucket array grows to millions of entries: it falls out of cache, must be cleared every pass, and the scatter thrashes address translation, so you lose more than the saved pass returns. Also budget the auxiliary output buffer, which roughly doubles peak memory. Then benchmark against the platform's general sort rather than trusting the arithmetic.
go deeper
Know that the base is a choice, not a given: a wider digit means fewer passes but more buckets. Being able to compute the pass count as key width divided by digit width is the expected depth here.
Explain both terms of d times (n plus k) and which one dominates at 100 million records. Show why the bucket array's size, cleared and scanned every pass, caps how wide the digit can usefully get.
Reason about the machine, not just the formula: cache residency of the bucket array, the scatter's access pattern, the auxiliary buffer's memory ceiling, and a benchmark against the general sort before committing.
Own the build-versus-use call. Weigh a measured speedup against permanently owning correctness for signed, mixed-width and out-of-alphabet keys, and against a memory ceiling that must hold across the whole fleet.
## The two knobs, and the fact that they fight LSD radix sort has one real tuning parameter: the digit width `b`. Everything else follows from it. - **Pass count** `d = ceil(w / b)`, where `w` is the key width. Wider digit, fewer passes. - **Bucket count** `k = 2^b` (or the alphabet size, for symbol-at-a-time digits). Wider digit, exponentially more buckets. The cost is roughly `d * (n + k)`. The `d * n` term is the real work — every pass reads all `n` records and writes all `n` records. The `d * k` term is overhead: per pass, the bucket structure must be zeroed, accumulated into offsets, and scanned. Widening `b` shrinks the first term linearly and inflates the second exponentially. ## Working the numbers for the scenario 100 million order codes, each 12 symbols of fixed length — call it 96 bits when handled as raw symbols. | Digit width | Passes `d` | Buckets `k` | Bucket array size | Notes | | --- | --- | --- | --- | --- | | 8 bits (one symbol) | 12 | 256 | ~1 KB | Fits the smallest cache; most passes | | 12 bits | 8 | 4,096 | ~16 KB | Still comfortably cached | | 16 bits (two symbols) | 6 | 65,536 | ~256 KB | Mid-level cache resident; half the passes of the 8-bit choice | | 24 bits | 4 | 16,777,216 | ~64 MB | Cleared every pass; scatter thrashes address translation | The `d * n` term at 8 bits is `12 * 10^8 = 1.2 * 10^9` record visits; at 16 bits it is `6 * 10^8`. The additive term at 16 bits is `6 * 65,536`, under half a million — negligible against 600 million. At 24 bits the additive term reaches roughly 67 million and, far worse, the bucket array no longer lives in cache: every scatter write goes to a random one of 16 million destinations, so the hardware's caching and address-translation machinery stops helping. The theoretical optimum from the formula alone would push `b` toward `log2(n)`, about 27 bits here, and that is exactly where the formula stops describing reality, because it charges the same price for a cached and an uncached memory touch. Real tuning lands at the largest `b` whose bucket array stays resident in fast cache. ## Why the alphabet-shaped choice matters too If the codes are decimal and you take one decimal digit per pass, you get 12 passes **and** a division and remainder per digit extraction. Taking raw fixed-width symbols instead lets digit extraction be a shift and a mask, and lets you pack two symbols into one wider digit. The lesson generalises: pick digits that align with how the key is physically laid out, so extraction is cheap and packing is free. A base chosen for human readability is almost always the wrong base. ## The costs the formula does not show - **Auxiliary space.** The standard formulation writes each pass into an output buffer of `n` records and alternates buffers, so peak memory is roughly twice the data. At 100 million records that is a real capacity decision, not a footnote. - **A counting pre-pass.** Many implementations count all `d` digit histograms in one initial sweep so later passes can skip the counting scan — cheap, and it makes the `d * k` term nearly vanish. - **Skippable passes.** If a digit position turns out to be identical across every record — common when a fixed-format code has a constant prefix or check character — that pass can be skipped entirely. Detecting that during the counting pre-pass is nearly free and can remove several passes on real-world identifier formats. ## Is it even worth it here? Run the comparison honestly. A general `n log n` sort at `n = 10^8` performs about `27 * 10^8` comparisons, each touching a multi-symbol key, with branch-heavy, cache-unfriendly access. Six radix passes perform `6 * 10^8` sequential read-and-scatter operations. The units are not directly comparable — a comparison and a record placement are different work — which is exactly why the answer must end at a benchmark on representative data and hardware rather than at the arithmetic. Typical outcomes for fixed-width keys at this scale are a multiple-times speedup, but that is an expectation to verify, not a guarantee. Weigh the ongoing cost too. A hand-rolled radix sort is code your team owns forever: signed keys, mixed-width keys, symbols outside the assumed alphabet, and the doubled memory ceiling all become your correctness problem. That is a fair price when this sort is on a critical path at 100 million records, and a poor one when the same data could be sorted once a night by the platform's general sort. ## The shape of a strong answer Name the two terms and say they pull against each other; pick `b` by cache residency of the bucket array rather than by the formula's optimum; account for the auxiliary buffer; mention the counting pre-pass and skippable constant digits; and finish with "then measure against the general sort, because the two cost models are not in the same units."
- Would you actually hand-roll this, or use the platform's general sort?Default to the general sort and make radix earn its place with a measurement on representative data. It is worth owning when the sort is on a hot path at this scale, the key format is genuinely fixed, and the doubled peak memory fits the budget. The lasting cost is correctness surface — signed or mixed-width keys, unexpected symbols, and endian assumptions become your team's bugs forever, not the platform's.
- The codes turn out to be variable-length, not always 12 symbols. What changes?LSD needs a uniform width, so you conceptually pad shorter keys and must decide what the pad sorts as; the result matches ordinary lexicographic order only if the pad ranks below every real symbol. MSD handles it natively — a key that runs out of symbols simply sorts ahead of the others in its bucket — and it can stop descending once a bucket is a singleton, which also saves passes on long keys.
- How would you cut the per-pass overhead of clearing and scanning the bucket array?Compute every digit position's histogram in a single initial sweep over the data, so each later pass reads a precomputed offset table instead of counting again. That sweep is one extra read of the input and it collapses the d times k term to almost nothing. It also reveals digit positions that are constant across all records, and those passes can be skipped outright.
saying these in an interview costs you the question
- Picks the base with no reference to bucket memory or cache
- Applies the formula's optimum of about log2(n) bits per digit literally
- Forgets the auxiliary output buffer doubles peak memory
- Compares pass counts to comparison counts as if the units matched
- Assumes radix always beats the platform sort at large n