Radix Sort: Digit Passes and Stability
Sort by the last digit, then the next, and so on to the first — each pass stable, so earlier work is never undone.
How Radix Sort Works
Radix sort solves the problem that breaks counting sort: a huge key range. Rather than allocating a counter for every possible value, it looks at one digit at a time, so the range per pass shrinks to 10 for decimal digits regardless of how large the numbers are. Sorting 32-bit integers needs ten passes over a range of ten, not one pass over a range of four billion.
- Find the widest number the digit count d decides how many passes are needed; shorter numbers are treated as left-padded with zeros.
- Start at the least significant digit sort the whole array by the ones digit only, using a stable sort.
- Move one digit left sort by the tens digit, then hundreds, and so on, always over the full array.
- Rely on stability at every pass equal digits keep the order the previous pass established, which is what makes lower digits still count.
- Stop after d passes the array is fully sorted, having never compared two whole numbers.
- One pass per digit, from least significant to most
- Each pass is a full stable sort of the whole array
- The digit range k is 10 for decimal, 2 for binary, 256 for bytes
- No two numbers are ever compared directly
Why Every Pass Must Be Stable
Stability is not an optimisation here — it is the correctness condition. After sorting by the ones digit, the array carries real information: among numbers with the same tens digit, the ones digits are already in order. The next pass must preserve that, and preserving the relative order of equal keys is exactly what stability means.
Suppose the tens pass reorders equal tens digits arbitrarily. Then 45 and 43, which the ones pass correctly put in the order 43, 45, could come out as 45, 43 — and nothing later will fix it, because no subsequent pass looks at the ones digit again. Every earlier pass is silently undone.
This is why counting sort is the standard per-digit engine: it is stable when its placement loop runs backwards, and it is O(n + k) with a tiny k for a single digit. Using an unstable sort like quicksort per digit produces a correct-looking algorithm that returns wrong answers — a classic exam trap, and worth being able to explain rather than just assert.
The direction also matters. Going least-significant-first (LSD) is what allows this stacking of passes. Most-significant-first (MSD) radix sort exists, but it works by partitioning into independent buckets and recursing, which is a different algorithm with different bookkeeping.
- Stability is a correctness requirement, not a nicety
- An unstable per-digit sort destroys every previous pass
- Counting sort is stable and O(n + k) — the natural engine
- LSD stacks passes; MSD partitions and recurses instead
Sort with radix sort
def counting_sort_by_digit(values, place):
counts = [0] * 10
for value in values:
counts[value // place % 10] += 1
# Cumulative counts, so counts[d] is one past the last slot for digit d.
for digit in range(1, 10):
counts[digit] += counts[digit - 1]
output = [0] * len(values)
# Backwards with a pre-decrement, so equal digits keep their order.
for value in reversed(values):
digit = value // place % 10
counts[digit] -= 1
output[counts[digit]] = value
return output
def radix_sort(values):
if not values:
return values
place = 1
while max(values) // place > 0:
values = counting_sort_by_digit(values, place)
place *= 10
return values
print(radix_sort([170, 45, 75, 90, 24]))#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// One stable counting-sort pass, keyed on a single digit.
vector<int> countingSortByDigit(const vector<int>& values, int place) {
vector<int> counts(10, 0);
for (int value : values) counts[value / place % 10]++;
// Cumulative counts, so counts[d] is one past the last slot for digit d.
for (int digit = 1; digit < 10; digit++) counts[digit] += counts[digit - 1];
vector<int> output(values.size());
// Backwards with a pre-decrement, so equal digits keep their order.
for (int i = (int)values.size() - 1; i >= 0; i--) {
int digit = values[i] / place % 10;
counts[digit]--;
output[counts[digit]] = values[i];
}
return output;
}
vector<int> radixSort(vector<int> values) {
if (values.empty()) return values;
int highest = *max_element(values.begin(), values.end());
for (int place = 1; highest / place > 0; place *= 10) {
values = countingSortByDigit(values, place);
}
return values;
}
int main() {
for (int v : radixSort({170, 45, 75, 90, 24})) cout << v << " ";
cout << endl;
return 0;
}import java.util.Arrays;
public class RadixSort {
// One stable counting-sort pass, keyed on a single digit.
static int[] countingSortByDigit(int[] values, int place) {
int[] counts = new int[10];
for (int value : values) counts[value / place % 10]++;
// Cumulative counts, so counts[d] is one past the last slot for digit d.
for (int digit = 1; digit < 10; digit++) counts[digit] += counts[digit - 1];
int[] output = new int[values.length];
// Backwards with a pre-decrement, so equal digits keep their order.
for (int i = values.length - 1; i >= 0; i--) {
int digit = values[i] / place % 10;
counts[digit]--;
output[counts[digit]] = values[i];
}
return output;
}
static int[] radixSort(int[] values) {
if (values.length == 0) return values;
int highest = Arrays.stream(values).max().getAsInt();
for (int place = 1; highest / place > 0; place *= 10) {
values = countingSortByDigit(values, place);
}
return values;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(radixSort(new int[]{170, 45, 75, 90, 24})));
}
}Step through it
Running on [170, 45, 75, 90, 24]
Cost, and When It Actually Wins
The cost is O(d(n + k)), where d is the number of digits and k the digit range. With d and k both treated as constants — fixed-width integers in a known base — that reduces to O(n), which does genuinely beat the O(n log n) comparison bound. The bound is not violated: radix sort never compares two elements, so it was never subject to it.
The honest caveat is that d is not always small, and log n is not always large. Sorting a thousand 9-digit numbers means 9 passes against log₂1000 ≈ 10 comparisons per element — no real win, and radix sort's memory traffic is worse. Radix sort earns its place on large n with small d: fixed-width IDs, dates, fixed-point currency, and byte-wise sorting of strings.
Memory is the other trade. Each pass needs an output buffer of size n plus counters of size k, so it is not in-place, and the repeated scattering of values across a buffer is unfriendly to caches. That is why a well-tuned quicksort often beats radix sort in practice even where the complexity says otherwise.
| Input | d | Passes vs log n | Verdict |
|---|---|---|---|
| 10^6 values, 6-digit IDs | 6 | 6 vs ~20 | Radix wins clearly |
| 10^3 values, 9-digit numbers | 9 | 9 vs ~10 | No real gain |
| 10^6 32-bit ints, byte-wise | 4 | 4 vs ~20 | Radix wins, k = 256 |
| Variable-length strings | varies | unbounded | Use MSD radix or a comparison sort |
- O(d(n + k)) — linear when d and k are constant
- No contradiction with O(n log n): nothing is compared
- Needs O(n + k) extra space and is cache-unfriendly
- The win is large n with few digits, not every integer sort
On Paper: Sorting [170, 45, 75, 90, 24]
Sort [170, 45, 75, 90, 24] by hand. The widest number has three digits, so three passes are needed and shorter numbers are read as left-padded — 45 is 045.
- Input:
[170, 45, 75, 90, 24] - Widest number: 170, so d = 3
- Each pass: a stable sort on one digit only
The ones pass keys on 0, 5, 5, 0, 4, giving [170, 90, 24, 45, 75]. Note 170 and 90 both key on 0, and 170 came first in the input, so it stays first — stability at work. Same for 45 before 75.
The tens pass keys on 7, 9, 2, 4, 7 of that new order, giving [24, 45, 170, 75, 90]. The hundreds pass keys on 0, 0, 1, 0, 0 and lands the three-digit 170 last: [24, 45, 75, 90, 170]. Three passes, fifteen digit reads, and not one comparison between two whole numbers.
- Ones pass:
[170, 90, 24, 45, 75] - Tens pass:
[24, 45, 170, 75, 90] - Hundreds pass:
[24, 45, 75, 90, 170] - Ties at each digit keep the previous pass's order — that is the algorithm working