THE RADIX SORT sort without comparing — digit by digit, from the punch-card era
Radix sort breaks the O(n log n) comparison barrier by never comparing: it sorts numbers digit by digit, using a stable pass on each digit from least to most significant. After the ones-digit pass and then the tens-digit pass, the whole array is ordered — because each pass is stable, earlier-sorted order survives within equal higher digits. It runs in O(n·k) for k-digit keys, and it is older than computers: Herman Hollerith sorted the 1890 US census this way on punch-card machines. No comparisons, just counting into bins.
THE TECHNIQUE stable pass per digit, LSD to MSD — O(n·k), no comparisons
The demo radix-sorts [32,15,43,21,54] by the ones digit, then the tens digit — fully sorted: live demo
HISTORY & CREDIT Herman Hollerith · 1887 (punch cards)
“Sorting needs comparisons.” — radix sort never compares two keys; it distributes by digit, stably, low to high. cited
the passes · a stable counting pass per digit, least-significant first. the invariant · stability preserves earlier order within equal higher digits — so LSD-to-MSD works. 1887 · Herman Hollerith — punch-card sorting; the 1890 US census.
Numbers filed digit by digit into bins — sorted with no comparison, a century before the computer. resource
RECOMMEND FOR I-13 the digit passes, on the compiler
On the canonical compiler, [32,15,43,21,54] sorted by ones then tens digit is fully ordered (lo 15, hi 54):
$ i13 run or_radixsort.i13 # stable pass per digit
RUN OK · 1482 step(s) · peak stack 15 · call depth 12
is_sorted = 1 lo = 15 hi = 54
Recommend as a NULL — resource, beating the comparison bound. Radix sort produces the same sorted output in O(n·k) without comparisons — it sidesteps the Ω(n log n) comparison bound (dart 512) by using the keys’ digit structure. That is a resource win (B40) via a representation the keys already have (B44). NULL — the oldest sort here, from the census machines.