The idea in brief
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.
Sorting digit by digit
Radix sort avoids comparisons entirely. It sorts numbers by processing one digit at a time, using a stable counting sort for each pass.
Sorting [170, 45, 75, 90, 802, 24, 2, 66] by units, then tens, then hundreds:
| Pass | Result |
|---|
| By units | [170, 90, 802, 2, 24, 45, 75, 66] |
| By tens | [802, 2, 24, 45, 66, 170, 75, 90] |
| By hundreds | [2, 24, 45, 66, 75, 90, 170, 802] |
Three passes, and the array is sorted. No two elements were ever compared with each other.
def radix_sort(arr):
if not arr:
return arr
max_val = max(arr)
exp = 1
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
counts = [0] * 10
for x in arr:
counts[(x // exp) % 10] += 1
for i in range(1, 10):
counts[i] += counts[i - 1] # cumulative positions
out = [0] * len(arr)
for x in reversed(arr): # backwards: preserves stability
d = (x // exp) % 10
counts[d] -= 1
out[counts[d]] = x
return out
Stability is not optional
The reversed(arr) on the second-to-last line is what makes the whole algorithm work.
Each pass must preserve the relative order established by the previous passes. If sorting by tens reordered two numbers that were already correctly ordered by units, the units pass would be wasted.
So radix sort requires a stable inner sort, and that is why counting sort's cumulative-position form — iterating the input backwards — is the version used. Using an unstable inner sort produces a wrong answer that looks nearly sorted, which is a confusing failure.
This is the clearest practical demonstration of why stability is a property worth caring about rather than a technicality.
Complexity, and the choice of base
O(d × (n + k)) where d = digits, k = base
The base is a tuning parameter, and the trade is direct: a larger base means fewer passes and a bigger count array.
| Base | Passes for 32-bit integers | Count array |
|---|
| 10 | 10 | 10 |
| 16 | 8 | 16 |
| 256 | 4 | 256 |
| 65,536 | 2 | 65,536 |
Base 256 — one byte per pass — is the usual choice for integers. Four passes, a 256-entry array, and the digit extraction is a bit shift and mask rather than division, which is considerably faster.
The complexity is linear in n for fixed-width keys, which beats the O(n log n) comparison lower bound. That is not a contradiction: the bound applies only to comparison-based sorts, and radix sort never compares.
| Sort | Complexity | Requires |
|---|
| Radix | O(d(n+k)) | Fixed-width integer-like keys |
| Counting | O(n+k) | Small integer range |
| Comparison sorts | Ω(n log n) | Only a comparison function |
What happens when the inner sort is not stable
The article says stability is non-negotiable for radix sort. That is a claim you can break on purpose: run the same algorithm with a stable inner pass and an unstable one, and watch the second produce a list that is simply wrong.
Guided experiments
- 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.
The short of it
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.
LSD and MSD
Least significant digit first is the version above: start with the rightmost digit and work left. It requires a stable inner sort and processes every digit of every element, and it is the standard choice for fixed-width numeric keys.
Most significant digit first starts from the left, partitions into buckets by the leading digit, and recurses into each bucket. It can stop early — once a bucket holds one element, that element's position is settled — which makes it better for variable-length keys such as strings.
MSD radix sort on strings is genuinely fast and is used for sorting large string collections. It is essentially a trie traversal, which is the connection worth noticing: MSD radix sort and tries organise data the same way.
| | LSD | MSD |
|---|
| Direction | Right to left | Left to right |
| Needs stability | Yes | No |
| Early termination | No | Yes |
| Suits | Fixed-width numbers | Variable-length strings |
| Recursion | None | Per bucket |
Handling the awkward cases
Negative numbers. The straightforward version breaks, because digit extraction treats sign as absent. Two fixes: offset every value by the minimum so all are non-negative, or partition into negatives and non-negatives, sort each, and reverse the negative part.
Floating-point numbers. IEEE 754 floats can be radix-sorted by reinterpreting their bits as integers, with a transformation to handle the sign bit and negative ordering. Correct, fiddly, and used in high-performance libraries.
Strings of unequal length. Pad conceptually with a character that sorts before everything, or use MSD radix sort, which handles it naturally.
Very large keys. The number of passes grows with key width, so a 512-bit key means many passes. Comparison sorts become competitive.
Where it is used
- GPU sorting libraries. Radix sort is the dominant GPU sorting algorithm, because its work is regular and highly parallel — no branching on comparisons.
- Database sorting of integer keys at scale.
- Suffix array construction, which uses radix sort internally and underlies compressed text indexes.
- Histogram-based image processing, where the count array is the histogram.
- Sorting fixed-width identifiers — timestamps, IDs, IP addresses.
- Bioinformatics, for sorting DNA k-mers over a four-letter alphabet.
The GPU case is the most consequential today: when sorting billions of keys on a GPU, radix sort's predictable memory access and absence of branching matter far more than its theoretical complexity.
Questions people ask
How does it beat O(n log n)? That bound applies to comparison-based sorts. Radix sort never compares two elements, so the bound does not apply.
Is it always faster than quick sort? No. It wins for fixed-width integer keys at large n; comparison sorts win for arbitrary objects, small n, or very wide keys.
Does the inner sort have to be counting sort? It has to be stable. Counting sort is the natural choice because it is O(n+k) and stable.
Can it sort strings? Yes — MSD radix sort handles variable-length strings well and is effectively a trie traversal.
What base should I use? 256 for integers: four passes for 32-bit keys, and digit extraction is a shift and mask.
Is it stable? LSD radix sort is, provided the inner sort is. That is a requirement, not a bonus.
Recap in one screen
- Sort by one digit at a time with a stable counting sort; after all digits, the array is sorted.
- Stability is mandatory — each pass must preserve the previous passes' ordering.
- O(d(n+k)), linear for fixed-width keys, which is possible because nothing is ever compared.
- Base 256 is the practical choice: four passes for 32-bit integers, with shift-and-mask digit extraction.
- LSD suits fixed-width numbers; MSD suits variable-length strings and is essentially a trie traversal.