Every comparison sort is stuck at O(n log n) — but if your keys are fixed-width integers, you can beat that by never comparing at all. Radix sort distributes numbers into 10 buckets by a single digit, gathers them back in bucket order, and repeats for the next digit up. The trick is the order: it must go least-significant digit first, and each pass must be stable. Step through the passes and watch a sorted array fall out with zero comparisons.
O(n · d) time · d = number of digits · stable, comparison-free
digit pass
One full round: bucket every number by one digit, then gather.
10 buckets
One per digit value 0–9. A number joins the bucket of its current digit.
stable gather
Numbers leave buckets in the exact order they entered — this preserves earlier passes.
LSD first
Least-significant digit first, working up to the most-significant.
radix.js — 10 buckets, one digit per pass
Ready
Eight numbers to sort. Each pass buckets them by one digit — starting at the units digit — then gathers bucket 0 through 9 in order. Step to distribute, step again to gather.
units
digit pass
–
phase
0
comparisons
How it works
Radix sort leans entirely on a stable counting pass per digit. Stability — numbers keep their relative order when their current digit ties — is what lets each pass preserve the work of every pass before it. Combined with going least-significant digit first, the final most-significant pass leaves the array fully sorted, because ties on the top digit are already broken by the lower digits sorted earlier.
1
Distribute by the current digit
Look at one digit of each number (units first) and drop the number into the matching bucket 0–9. Numbers with the same digit stack in arrival order.
2
Gather in bucket order
Concatenate bucket 0, then 1, … then 9, keeping each bucket’s internal order. The array is now sorted by that one digit — stably.
3
Move to the next digit up
Repeat on the tens digit, then hundreds, and so on. Because each pass is stable, the higher-digit pass keeps lower digits sorted among ties.
✓
Why least-significant first?
Sorting the most-significant digit first would let a later (lower-digit) pass scramble the top-level order. Going LSD-first with stable passes means the last, top-digit pass sees an array already sorted on everything below it.
Time
O(n · d)
Comparisons
0
Stable
Yes (required)
Beats
O(n log n)
The code
# LSD radix sort for non-negative integers, base 10def radix_sort(a):
ifnot a: return a
max_d = len(str(max(a)))
for d in range(max_d): # units, tens, hundreds, ...
buckets = [[] for _ in range(10)]
for x in a:
digit = (x // 10**d) % 10
buckets[digit].append(x) # stable: arrival order kept
a = [x for b in buckets for x in b] # gather 0..9return a # sorted, zero comparisons
Quick check
1. What makes radix sort able to beat the O(n log n) comparison-sort bound?
The Ω(n log n) bound is for comparison-based sorts. Radix sort makes zero comparisons — it buckets by digit — so the bound simply doesn’t apply. Its cost is O(n·d) where d is the number of digits.
2. Why must each digit pass be stable?
Stability keeps equal-digit numbers in their arrival order. That’s what lets the tens pass keep the units order among numbers with the same tens digit — so the final array is sorted on all digits, not just the last one processed.
3. Why go least-significant digit first?
LSD-first + stable passes means each higher-digit pass only needs to break ties, since the lower digits were already ordered. Most-significant-first would let later passes scramble the top-level order.
FAQ
What is radix sort?
A non-comparison sort for integers or fixed-width keys. It processes one digit at a time — bucketing numbers by that digit and gathering them back — repeating per digit. It runs in O(n·d) time, beating the O(n log n) comparison bound.
How does radix sort beat O(n log n)?
The O(n log n) bound is only for comparison sorts. Radix sort never compares elements — it buckets them by digit — so the bound doesn’t apply. Its time is O(n·d), effectively linear for fixed-width integer keys.
What is the difference between LSD and MSD radix sort?
LSD (least-significant digit) processes digits last-to-first with a stable pass each, simple and great for fixed-width keys. MSD (most-significant digit) goes first-to-last and recurses into buckets, handling variable-length keys and early stopping, but is more complex.
When should you not use radix sort?
When keys are long or unbounded (large d), can’t be broken into digits (arbitrary objects with a comparator), or bucket memory is tight. For general comparison sorting of arbitrary items, an O(n log n) sort like quicksort or mergesort is the better default.