Radix Sort
Algorithms & Data
Almost every sort you've seen works by comparing pairs of values.
Radix sort doesn't: it tallies how many of
each digit there are, turns those tallies into positions, and drops each value straight into its
slot — no comparisons at all. Watch a row of bars re-bucket, one digit at a time, until they land
in a clean ascending gradient. Runs on its own; no joypad needed. Written in C and compiled with
the llvm-mos-based 65816 toolchain
(+mos-a16, 16-bit accumulator mode).
Self-running demo — bars re-bucket pass by pass, then reshuffle.
Click the screen to focus, then watch. Tab away and it pauses.
What it is
Radix sort orders numbers by their digits, least-significant first, using counting sort at each step:
for each value: count[digit(value)]++; // 1. histogram prefix-sum the counts into starting offsets; // 2. offsets for each value: out[count[digit]++] = value; // 3. stable scatter // ...repeat for the next digit. No comparisons anywhere.
No element is ever compared to another — the whole thing is tallies and array moves. Here the bars are coloured by value, so a sorted array reads as a clean low-to-high gradient. It stays bit-exact across every codegen mode.
Compiler stress-test
| Item | What it exercises |
|---|---|
| no comparisons | Quicksort, heapsort and mergesort all work by comparing pairs of elements. Radix sort never does: it counts how many of each digit there are, turns those counts into positions, and drops each element straight into its slot. A different loop nest — reads, writes and running sums, no compares. |
| histogram + prefix + scatter | Three passes over the array: tally each digit, prefix-sum the tallies into offsets, then place each element at its offset (bumping the offset so equal keys stay in order). It sorts one digit at a time, least-significant first. |
| stable by construction | Because equal digits are scattered in the order they appear, earlier passes are preserved by later ones — which is exactly what makes least-significant-digit radix sort correct. |
| cross-checked | The build gate verifies each result is both sorted (no out-of-order pair) and a true permutation of the input (same xor and sum), so any slip in the count/prefix/scatter is caught. |
Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg
(and MAME where the SPC700 IPL is present). Hit Verify fidelity to reproduce the build
gate's WRAM assert (gate CRC 0x123E — the sorted output of many random arrays, each
checked for order and for being a true permutation) live in this tab. No far pointers — the same
source passes every way: host == default == +mos-a16 == +mos-xy16 ==
bsnes-jg, -verify clean.