In LSD radix sort, why must every digit pass be stable for the final order to come out correct?
answer
- what does one pass actually order?
- think about records tying on this digit
- state the invariant after pass p
- ties must keep their arrival order
- arrival order encodes the earlier digits
basics
~20 sEach pass sorts on one digit only. Stability is what preserves the ordering earlier passes established among records that tie on the current digit. Break stability in a single pass and every lower digit's work is scrambled.
solid answer
~50 sLSD radix sort maintains an invariant: after the pass on digit position `p`, the array is sorted by the `p+1` least significant digits. The pass itself only orders records whose digit `p` differs — records tying on digit `p` are simply emitted in the order they arrived, and by the invariant that arrival order is exactly the ordering by digits `0..p-1`. A stable pass therefore extends the invariant one digit at a time; an unstable pass permutes those ties arbitrarily, destroying the invariant, and the final array ends up ordered by the most significant digit with garbage inside each group. This is why LSD is always paired with a stable inner distribution pass. MSD radix sort is different: it recurses into disjoint buckets, so it does not need cross-pass stability, though it still needs a stable partition to keep equal whole keys in their original order.
code
pseudocode · 13 lines// a[] holds n keys of d digits in base k
for pos in 0..d-1:
for b in 0..k-1:
bucket[b] = empty
for i in 0..length(a)-1:
digit = (a[i] / k^pos) mod k
add a[i] to the end of bucket[digit] // appending keeps arrival order
idx = 0
for b in 0..k-1:
for each x in bucket[b], in the order added:
a[idx] = x
idx = idx + 1
// invariant: after pass pos, a[] is sorted by digits 0..posgo deeper
Know that LSD radix sort makes one pass per digit starting from the least significant one, and that each pass must keep tied records in the order it found them. Being able to trace three or four short keys by hand is enough here.
State the invariant explicitly — after pass p the data is sorted on the p+1 lowest digits — and show why a stable pass extends it. Being able to construct a small counterexample where an unstable pass breaks the result is the expected depth.
Connect the requirement to implementation choices: the inner pass is a bucketed distribution precisely because appending is stable, and swapping in a faster unstable inner sort silently corrupts output rather than merely slowing it down.
Frame stability as a contract the surrounding system may already depend on. Decide whether the pipeline's ordering guarantees are documented and tested, since a stability regression here produces wrong data, not a visible crash.
## The invariant is the whole algorithm LSD radix sort makes `d` passes over the data, starting at the least significant digit. Its correctness rests on one loop invariant: > After the pass on digit position `p`, the array is sorted by the `p+1` least significant digits, treated as a number (or as a suffix of the key). Prove it by induction. Before any pass, the invariant holds vacuously. Suppose it holds after pass `p-1`. Pass `p` orders records by digit `p`. For two records whose digit `p` differs, the pass places them correctly by definition. For two records whose digit `p` is **equal**, the pass performs no ordering work at all — it emits them in the order it found them. If the pass is stable, that order is the pre-pass order, which by the induction hypothesis is the correct order on digits `0..p-1` — exactly the tiebreak the lexicographic comparison calls for. So the invariant extends to digits `0..p`. After the last pass, the array is sorted by all `d` digits. Stability is not a nicety here. It is the mechanism by which the previous pass's result is carried forward. Without it, each pass throws away everything before it. ## Trace it, then break it Take five three-digit codes: `481, 152, 486, 157, 480`. - **Pass on the last digit** (1, 2, 6, 7, 0): `480, 481, 152, 486, 157`. - **Pass on the middle digit** (8, 8, 5, 8, 5): the two records with middle digit 5 are `152, 157` in that arrival order, and the three with middle digit 8 are `480, 481, 486` in that arrival order. Result: `152, 157, 480, 481, 486`. - **Pass on the first digit** (1, 1, 4, 4, 4): the ties keep their order, so the array is unchanged and now fully sorted. Now make the middle pass unstable — suppose it emits the three records with middle digit 8 as `486, 480, 481`. The array after that pass is `152, 157, 486, 480, 481`. The final pass sees first digits `1, 1, 4, 4, 4`; every tie is preserved, so the output is `152, 157, 486, 480, 481` — wrong, and wrong specifically in the last digit, the very first thing the algorithm sorted on. That is the signature failure: the output looks plausible from the left and is garbage from the right. ## Why the inner pass is a distribution, not a general sort Because the digit alphabet is small (base `k`), the natural inner pass is a bucketed distribution that appends records to `k` buckets in scan order and concatenates the buckets in digit order. Appending preserves arrival order inside each bucket, so this construction is stable by design, and it costs `O(n + k)` per pass — hence the overall `O(d(n + k))`. Reaching for a general-purpose sort as the inner pass is both slower and a stability hazard, since many fast general sorts are unstable. ## LSD versus MSD on this point MSD radix sort partitions on the **most** significant digit first, then recurses inside each bucket on the next digit. Its buckets are disjoint groups that never mix again, so the correctness of an MSD sub-sort does not depend on preserving an earlier pass's order across the whole array. MSD needs stable partitioning only if you want records with fully equal keys to retain their original relative order. That structural difference buys MSD two things. It can stop descending as soon as a bucket holds one record (or holds records already known to be equal), so it need not read every digit of every key; and it handles variable-length keys naturally, since a key that runs out of digits simply sorts before the others in its bucket. It costs recursion bookkeeping and, with many small buckets, a scattered memory access pattern. LSD's fixed `d` passes are simpler, branch-predictably regular, and easy to reason about — which is why LSD dominates for fixed-width keys. ## The property you get for free Because every pass is stable, the entire LSD pipeline is stable: records with identical keys come out in their input order. When you are sorting by one field and a previously established order on another field must survive, that is a genuine reason to choose this family over a fast unstable sort. Remember the precise meaning, though: stability promises order among **equal keys only**, and it is meaningless when equal records are indistinguishable. ## The wrong answers to avoid "Stability only matters if you care about duplicates" is the classic miss — for LSD, stability is a correctness requirement even when every key is distinct, because ties on a single digit are common regardless. Equally wrong is "the last pass is the important one, the earlier ones just help": every pass is load-bearing, and the earliest pass is the one an unstable later pass destroys.
- When would you reach for MSD radix sort instead of LSD?When keys are long or variable-length and most pairs diverge in the first few digits. MSD partitions on the leading digit and recurses into disjoint buckets, so it can stop as soon as a bucket holds a single record and never reads the rest of those keys; it also handles variable lengths without padding. The price is recursion bookkeeping and a scattered access pattern across many small buckets, which is why LSD usually wins on fixed-width keys.
- Does LSD radix sort preserve the input order of records with identical keys?Yes. Every pass is stable and stability composes, so the whole pipeline is stable: equal keys emerge in input order. That makes it a legitimate choice when a secondary ordering established earlier has to survive the sort. The guarantee applies to equal keys only — it says nothing about records that differ, and it is vacuous when equal records carry no distinguishing payload.
- Could you run the passes from most significant to least significant and still use the LSD structure?No. Sorting by the most significant digit last is what makes LSD work, because the final pass dominates and earlier passes survive only inside its ties. Reversing the order means the last pass sorts by the least significant digit and overwhelms everything before it, leaving the array ordered by the wrong digit. Processing most-significant-first requires the recursive MSD structure with disjoint buckets instead.
Think of sorting index cards into piles by their last letter, stacking the piles up, then re-dealing by the previous letter. If you shuffle a pile before stacking it, the previous round's work is simply gone.
saying these in an interview costs you the question
- Says stability only matters when duplicate keys exist
- Thinks only the final pass really determines the order
- Believes an unstable inner pass just reorders equal records harmlessly
- Claims LSD works equally well running most significant digit first
- Cannot state what the array is sorted by mid-algorithm