Sort by the last digit, then the next, then the next. No two values are ever compared — which is how radix sort slips past the O(n log n) barrier that binds every comparison sort.
Controls
values8
for d in digits(least→most):
buckets = [[] for _ in range(10)]
for x in a:
buckets[digit(x,d)].append(x)
a = concat(buckets) # stable
Digit Passes
step 0
Current array
Buckets 0–9
Insight
Radix sort never compares two values. It distributes by digit and relies on the bucketing being stable — equal keys keep their previous relative order.
pass0
digit place–
comparisons0
operations0
Complexity
TimeO(d·n)
SpaceO(n+k)
Comparisons0
Radix Sort
Sorting without ever asking which of two values is bigger.
Quick Context
Radix sort processes numbers one digit at a time, distributing them into buckets by that digit and collecting them back. Repeat for every digit position — least significant first — and the array emerges sorted, with zero comparisons.
Why Stability Is Non-Negotiable
This is the crux. When sorting by the tens digit, two numbers with the same tens digit must retain the order they got from the units pass — otherwise that earlier work is destroyed.
A stable bucketing preserves relative order of equal keys, so each pass refines the previous one instead of undoing it. Watch numbers entering a bucket: they always append to the end, never jump the queue. Swap in an unstable bucketing and radix sort simply stops working.
Least Significant Digit First
It feels backwards to start with the last digit, but it is what makes stability sufficient. After the units pass, the array is sorted by units. After the tens pass, it is sorted by tens with units breaking ties — because stability preserved them. After the hundreds pass, fully sorted.
Step through and check the array after each pass: it is correctly sorted by all digits processed so far.
Beating the O(n log n) Barrier
Any sort that works by comparing elements needs at least O(n log n) comparisons — that is a proven lower bound, not an engineering limitation. Merge sort and heap sort sit exactly on it.
Radix sort escapes because it never compares. Its cost is O(d · n) for d digits, which is linear in n when d is fixed. There is no contradiction: the lower bound only constrains comparison sorts.
The Catch
It needs O(n + k) extra space for buckets — it does not sort in place.
It only works on keys decomposable into digits: integers, fixed-length strings, dates. Arbitrary objects with a custom comparator are out.
The d factor matters. For 64-bit integers d can be large enough that O(n log n) wins in practice.
Cache behaviour is poor — scattering into buckets jumps around memory.
Its sweet spot is large volumes of fixed-width keys, which is why it appears in database index construction and older card-sorting machinery — literally where the algorithm came from.
Interactive Exploration Guide
Step through pass 1 (units). Values scatter into buckets by their last digit and are collected back in bucket order.
Check the array after pass 1. It is sorted by units only — the tens are still scrambled.
Watch pass 2. Numbers sharing a tens digit stay in their pass-1 order. That is stability doing the real work.
Note the comparison counter: zero. No two values are ever compared, which is exactly how the O(n log n) bound is sidestepped.
Count the passes. Three-digit numbers need three passes, regardless of how many values there are.
Key Takeaway
Radix sort distributes by digit rather than comparing, achieving O(d·n) — linear when digit count is fixed. It depends entirely on stable bucketing, since each pass must preserve the ordering established by the last. Only usable on digit-decomposable keys, and it costs extra memory.
Cheat sheet
Radix Sort
Sort by the last digit, then the next, then the next. No two values are ever compared — which is how radix sort slips past the O(n log n) barrier that binds every comparison sort.