Radix sort
mediumLeast-significant digit first looks backwards but is the only order that works with a stable sub-sort: each pass refines the last without destroying it. Genuinely linear for fixed-width keys.
O(d(n + b))Average O(d(n + b))Worst O(d(n + b))Space O(n + b)StableNeeds extra memorySaved in this browser - no sign-up, nothing sent anywhere.
How radix sort works
Sort three-digit numbers by their units digit, then by tens, then by hundreds - and after the last pass the array is fully sorted. Each pass distributes values into ten buckets by one digit and collects them back in bucket order 0..9. Least-significant-first looks backwards, but it is the only order that works with a simple pass structure: each pass refines the previous ordering instead of destroying it.
Stability is load-bearing. Within a pass, values landing in the same bucket keep their arrival order, so when two numbers tie on the hundreds digit, the order the tens pass gave them survives as the tiebreak. This module appends to ten bucket lists and flattens - stable by construction. Classic implementations run counting sort per digit instead; same idea, tighter memory.
The cost is O(d(n + b)): d digit passes, each touching n values and b buckets. For fixed-width keys d is a constant - the ten 3-digit values here take exactly 3 passes and 30 placements with zero comparisons - so radix sort is genuinely linear where comparison sorts cannot be. The radix is tunable: base 256 sorts 32-bit integers in 4 passes of 256 buckets.
Step by step
- Sort [329, 457, 657, 839, 436, 720, 355, 174, 92, 610]. The largest value, 839, has three digits - so three passes.
- Units pass: 720 and 610 land in bucket 0, 457 then 657 in bucket 7, 329 then 839 in bucket 9. Collecting gives [720, 610, 92, 174, 355, 436, 457, 657, 329, 839].
- Tens pass: bucket 5 receives 355, 457, 657 in that order - the units ordering survives inside the bucket. Collecting gives [610, 720, 329, 436, 839, 355, 457, 657, 174, 92].
- Hundreds pass: 92 has hundreds digit 0 and leads bucket 0; every value finds its final bucket.
- Collecting yields [92, 174, 329, 355, 436, 457, 610, 657, 720, 839] - sorted after 30 placements and zero comparisons.
- Note 457 and 657: tied on units digit 7 and tens digit 5, they travelled side by side until the hundreds pass finally separated them.
Complexity
| Best case time | O(d(n + b)) |
|---|---|
| Average time | O(d(n + b)) |
| Worst case time | O(d(n + b)) |
| Space | O(n + b) |
d digits, b buckets. For 32-bit integers d is a constant.
Reference implementation
Python
def radix_sort(a):
if not a:
return a
exp = 1
while max(a) // exp > 0:
buckets = [[] for _ in range(10)]
for x in a: # stable distribution
buckets[(x // exp) % 10].append(x)
a = [x for b in buckets for x in b]
exp *= 10
return aJavaScript
function radixSort(a) {
if (!a.length) return a;
const max = Math.max(...a);
for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
const buckets = Array.from({ length: 10 }, () => []);
for (const x of a) buckets[Math.floor(x / exp) % 10].push(x);
a = buckets.flat();
}
return a;
}Worth noticing
Least significant digit first, and that order matters
Sorting by the units digit first, then tens, then hundreds, looks backwards but is the only order that works with a stable sub-sort: each later pass refines the previous one without destroying it.
Stability is load-bearing here
When two numbers share a hundreds digit, their relative order was fixed by the tens pass and must survive. Swap the bucket sort for an unstable one and radix sort simply stops working.
O(d · (n + b)) - linear when d is small
d digits, b buckets. For fixed-width keys like 32-bit integers or dates, d is a constant and radix sort is genuinely linear - which is how it beats the comparison lower bound.
Common pitfalls
- Using an unstable sort for the per-digit pass. Later passes scramble the order earlier passes established, and the algorithm simply stops producing sorted output.
- Distributing by the most significant digit first while still collect-and-flattening: the units pass then wrecks the leading-digit grouping. MSD radix needs per-bucket recursion, a different algorithm.
- Mishandling shorter numbers. 92 must behave as 092 - a hundreds digit of 0. Integer division gives that for free here, but string keys need explicit padding to a common length.
- Feeding it negative numbers raw: digit extraction on negatives breaks bucket order. Split by sign and sort each side, or offset the values first.
- Calling it unconditionally linear. d = log base b of the maximum value, so for keys whose width grows with n the cost is effectively O(n log n) - the linearity claim is about fixed-width keys.
Where it is used
- GPU sorting: radix sort is the standard high-throughput sort in CUDA and Thrust for fixed-width integer keys.
- Fixed-length string keys - dates in YYYYMMDD form, zero-padded IDs, IP addresses - one pass per position.
- Suffix array construction and Burrows-Wheeler pipelines, which radix-sort tuples in linear time.
- The interview follow-up to counting sort: what to do when values are large but fixed-width.
Frequently asked questions
What is the time and space complexity of radix sort?
O(d(n + b)) in every case: d digit passes, each distributing n values across b buckets - here 3 passes, 10 buckets. Space is O(n + b) for the buckets. For fixed-width keys like 32-bit integers d is a constant, which makes the total effectively linear in n.
Why does radix sort go least significant digit first?
Because each stable pass preserves everything the previous passes decided. After the tens pass, numbers sharing a tens digit are already ordered by units; the hundreds pass keeps that as its tiebreak. Most-significant-first would need each bucket sorted recursively on its own - collecting and flattening would destroy the leading grouping.
Does radix sort work on negative numbers or floats?
Not directly. Negatives need a sign split - sort negatives and non-negatives separately, then concatenate with the negative block reversed appropriately - or an offset into a non-negative range. Floats can be radix-sorted through an IEEE 754 bit trick: flip the sign bit, and all bits for negatives, and the bit patterns order like the numbers.
Is radix sort faster than quicksort?
On large arrays of fixed-width integer keys, often yes - O(n) passes beat O(n log n) comparisons, which is why GPUs standardise on it. But each pass costs memory traffic and O(n + b) space, and it cannot take an arbitrary comparator. For general data with custom orderings, comparison sorts keep the job.