How LSD radix sort actually works

A companion to the main post. The main post measures what a radix sort costs and why it walks around the comparison wall on fixed-width integer keys; this page is about the mechanism underneath — what "sort by distributing keys into buckets" actually compiles to, and why starting from the least-significant digit is the part that makes it correct. If you can read a little pseudocode, you can follow it.

The one idea: sort by digit, never compare#

std::sort works by comparing pairs of keys. Radix sort never compares anything. Given keys that are fixed-width integers, it looks at one digit at a time and drops each key into a bucket for that digit — and if you do this from the least-significant digit up to the most, the keys come out fully sorted. That's the whole trick. The main post explains why sidestepping comparison lets radix beat the Ω(n log n) wall; this page shows the machine doing it.

The animation runs the real algorithm on a small array — eight two-digit numbers, base 10, so you can read every step. (The real code uses a bigger radix for cache reasons, which is the last section here; the mechanism is identical.)

One pass, three phases#

for (auto k : a) ++count[(k>>s)&0xFF];        // 1 histogramfor (b) { count[b]=sum; sum+=cnt[b]; }        // 2 prefix sumfor (auto k : a) tmp[count[(k>>s)&0xFF]++]=k; // 3 scattera.swap(tmp);                                  // 4 ping-pong

Each pass over the array is a counting sort on one digit, and it's three sweeps:

1. Count. Walk the array; for each key, increment a counter for its current digit. At the end you know how many keys fall in each bucket — but nothing has moved yet.
2. Positions (the prefix sum). Turn those counts into starting positions in the output. Bucket 0 starts at 0; bucket 1 starts wherever bucket 0's run ends; bucket 2 after that. It's a running total across the buckets, and it's the step that decides where each bucket's block of keys will live.
3. Scatter. Walk the array again; write each key into its bucket's current position, then advance that position by one. Keys with the same digit land in consecutive slots, in the order the sweep met them.

Then the output buffer becomes the input for the next digit, and you repeat. Four passes for a 32-bit key, and you're done.

Why least-significant-first works#

Watch the scatter closely — it's the part a benchmark can't show you. Because both the count sweep and the scatter sweep run left-to-right, and the scatter advances each bucket's pointer as it writes, two keys with the same digit come out in the same relative order they went in. That property has a name: the pass is stable.

Stability is the reason the whole thing works. Follow the four keys the animation highlights at the end — 42 43 45 48:

start       45 12 48 91 42 18 43 15
after ones  91 12 42 43 45 15 48 18   — ordered by the last digit
after tens  12 15 18 42 43 45 48 91   — ordered by both, i.e. sorted

Pass 2 groups the keys by their tens digit, so 42 43 45 48 end up together in the "4" group. Their order within that group — 2, 3, 5, 8 — is exactly what pass 1 left behind, because pass 2's stable scatter never reorders keys that share a tens digit. The ones-digit ordering survives underneath the tens-digit ordering. Do that for every digit position and you have sorted the whole key, one digit at a time, without a single comparison.

It has to be least-significant-first for this to hold: each pass refines the previous one only because stability preserves it. Go most-significant-first and each pass would scramble the previous pass's work — unless you recursed separately into every bucket, which is a different, more complicated algorithm.

Why bytes, not decimal digits#

The demo uses base 10 because ten buckets are easy to look at. The real code uses base 256 — one byte per pass — so a 32-bit key is four passes and a 64-bit key is eight. Two reasons the byte is the right radix:

• The histogram stays in L1. 256 counters is a couple of kilobytes; it lives in the fastest cache, and the count sweep becomes a stream of cheap increments.
• Extracting a byte is one instruction. (k >> shift) & 0xFF is a shift and a mask — no division, no branch. A decimal digit would cost a divide per key per pass.

The passes-per-key is also the knob the main post's key-width result turns on: a wider key means more passes, which is why radix's lead over std::sort erodes as keys get wider — the main post measures exactly how much between 32- and 64-bit keys. Everything else about the three phases is unchanged; only the bucket count and the pass count move.

What it costs, and when to reach for something else#

Radix buys its linear cost with memory. It needs a second array the size of the input to scatter into, and it ping-pongs between the two — the O(n) scratch buffer the main post charges it for, and the reason the small-N picture there is messier than the asymptotics suggest.

The precondition is also strict: the keys have to decompose into fixed-width digits. Floating-point, strings, variable-length records — anything you can only order by comparing — radix can't touch, and std::sort is the right default there. What radix gives you, on the narrow shape where it applies, is a sort whose cost doesn't depend on the order of the input at all. That's the property that matters when the thing you're bounding is a tail, not an average — which is where the main post picks the argument back up.

Further reading#

1. CLRS, Introduction to Algorithms, §8.2–8.3 — counting sort and radix sort, the canonical treatment. The count / prefix-sum / scatter above is straight out of §8.2.
2. McIlroy, Bostic & McIlroy, "Engineering Radix Sort," Computing Systems 6(1), 1993, pp. 5–27. The practical engineering paper. It's aimed at string keys sorted byte-by-byte left to right, and presents three methods — including the in-place "American flag" sort — but the cache and bucket-handling lessons carry straight over. PDF via Doug McIlroy's publications page.
3. Malte Skarupke, "I Wrote a Faster Sorting Algorithm" — a modern, heavily engineered radix sort with an honest account of where it wins and loses against a good comparison sort.

What you don't need to follow this#

• The most-significant-digit (MSD) variants. They recurse into buckets and can beat LSD on some inputs; the LSD version here is the one in the demo and the easiest to see whole.
• SIMD, software prefetch, and the other tricks production radix sorts use to hide the scatter's memory latency. They make it faster; they don't change what it's doing.