Radix sort never compares two values against each other. Instead it looks at one digit at a time, starting from the rightmost, and distributes every value into one of ten buckets based on that digit. After each pass, the values are collected back in bucket order. After enough passes to cover every digit, the array is sorted.
Press play, or step through it one placement at a time. Orange highlights the value whose digit is being read. Yellow marks a position being written during the collect-back phase. Green means fully sorted.
Ready. 10 values, unsorted.
0 comparisons · 0 placements
Ready. 10 values, unsorted.
- Comparing
- Placing
- Sorted
Code
- def radix_sort(a):
- if not a:
- return a
- max_val = max(a)
- exp = 1
- while max_val // exp > 0:
- buckets = [[] for _ in range(10)]
- for val in a:
- digit = (val // exp) % 10
- buckets[digit].append(val)
- a = []
- for bucket in buckets:
- a.extend(bucket)
- exp *= 10
- return a
Try Sorted and Reversed. Both take exactly the same number of passes and the
same number of placements, because radix sort does not look at the overall order
at all. It processes digits mechanically. That predictability is the trade: no
best case, but no worst case either.
Time and space complexity
| Case | Complexity | Why |
|---|---|---|
| Best | O(nk) | Always does k full passes over n values, regardless of input order. |
| Average | O(nk) | Same. The input order changes nothing. |
| Worst | O(nk) | Same. No input can make radix sort slower or faster. |
| Space | O(n + b) | The buckets hold all n values; b is the base (10 for decimal). |
| Stable | Yes | Equal digits preserve their prior order because the sub-sort is stable. |
Here k is the number of digits in the largest value. For values up to 99 that is 2; for values up to 999 it is 3. Because k depends on the data range rather than n, radix sort is often described as linear — but only when the key length is bounded.
Step by step
- Find the largest value to know how many digit positions to process.
- Start with the ones digit (rightmost).
- For each value, read that digit and place the value into the corresponding bucket (0 through 9).
- Collect all values back from the buckets in order: bucket 0 first, then bucket 1, and so on.
- Move to the next digit position (tens, hundreds, ...) and repeat from step 3.
- After processing the most significant digit, the array is sorted.
The key insight: because each pass is stable, the order established by earlier passes is preserved within each bucket of later passes. The ones digit sorts by ones; then the tens pass groups by tens but keeps the ones order within each group.
Worked example
Sorting [53, 89, 14, 72]:
| Pass | Digit | Buckets (non-empty) | Array after |
|---|---|---|---|
| 1 | Ones | 2: [72], 3: [53], 4: [14], 9: [89] | [72, 53, 14, 89] |
| 2 | Tens | 1: [14], 5: [53], 7: [72], 8: [89] | [14, 53, 72, 89] |
Eight digit inspections and eight placements into buckets, plus eight collect-back writes. Two passes because the largest value (89) has two digits. No comparisons at any point.
When to use it
| Reach for it when | Avoid it when |
|---|---|
| You have many values with short, fixed-width keys (integers, fixed-length strings) | Keys are long or variable-length and k dominates n |
| You need guaranteed linear-time performance and the key length is bounded | Memory is constrained — it needs O(n) extra space |
| Stability matters and you want it without the O(n log n) overhead of merge sort | The data is already nearly sorted and you want an adaptive algorithm |
| You are sorting millions of records by a numeric field | The values are floating-point numbers or complex objects with no natural digit decomposition |
The code
Every version below is LSD (least significant digit), base 10, processing right to left. It produces the same result as the visualiser above.
def radix_sort(a):
if not a:
return a
max_val = max(a)
exp = 1
while max_val // exp > 0:
buckets = [[] for _ in range(10)]
for val in a:
digit = (val // exp) % 10
buckets[digit].append(val)
a = []
for bucket in buckets:
a.extend(bucket)
exp *= 10
return a
nums = [53, 89, 14, 72, 31, 67, 45, 98, 26, 80]
result = radix_sort(nums)
print(result)
Common questions
What is the time complexity of radix sort?
O(nk), where n is the number of values and k is the number of digits in the largest value. For fixed-width integers k is a constant, so in practice it runs in linear time. But k grows with the range of the data, so calling it O(n) without qualification is misleading.
Is radix sort a comparison sort?
No. It never asks whether one value is greater than another. It reads individual digits and distributes values into buckets by those digits. That is how it sidesteps the O(n log n) lower bound that applies to comparison sorts.
Is radix sort stable?
Yes, provided the sub-sort used at each digit position is stable. The standard implementation uses counting sort, which preserves the order of equal keys. That stability is essential: earlier passes established an order that later passes must not destroy.
LSD or MSD — what is the difference?
LSD (least significant digit) processes digits from right to left and is simpler: one flat loop per digit, no recursion. MSD (most significant digit) processes left to right and recurses into sub-buckets, which makes it natural for variable-length strings but harder to implement for integers. This page shows LSD.
Why does radix sort need O(n + k) space?
It needs somewhere to put the values while redistributing them. The bucket array holds all n values across 10 buckets (for base 10), and the bucket structure itself takes space proportional to the base. With base 10 that is 10 lists totalling n entries, so O(n + 10) which simplifies to O(n).
When is radix sort faster than quicksort?
When the keys are short relative to n. Sorting a million 32-bit integers takes radix sort about 10 passes (base 10) or 4 passes (base 256) with linear work per pass, while quicksort does roughly 20 million comparisons. The crossover depends on cache behaviour and the constant factors, but for large n with bounded key length, radix sort wins.