Overview
Radix Sort sorts numbers one digit at a time, starting from the least significant digit and working up. Each pass is a stable bucket distribution — normally counting sort — and after the final digit the whole array is in order.
The result looks like sleight of hand: at no point does the algorithm compare two full numbers, yet they come out sorted. What carries the order forward is stability. Because each pass preserves the relative order established by the previous one, sorting by the tens digit keeps the units digit ordering intact inside every group.
How Radix Sort works
- Find the largest value to know how many digits d the longest key has.
- Start at the least significant digit — the units place.
- Distribute every element into buckets by that digit, using a stable pass so equal digits keep their existing order.
- Collect the buckets back into the array in bucket order, then move to the next digit up.
- Repeat for all d digits. After the most significant pass the array is fully sorted.
When to use it
- Large volumes of fixed-width integers: IDs, zip codes, timestamps, IP addresses treated as 32-bit values.
- Fixed-length strings sorted lexicographically, where each character position is a digit.
- Sorting on external storage or in hardware, where the fixed, data-independent access pattern matters more than the constant factor.
- Weak when keys are long relative to n — sorting a hundred 20-digit numbers means twenty passes to order a hundred items.
Complexity analysis
Time is O(d · (n + b)) where d is the number of digit positions and b the base, so with a fixed key width it is linear in n. That d is easy to overlook: it is effectively log_b(max value), which is why radix sort is not 'linear sorting' in general, only linear for keys of bounded width. Space is O(n + b) for the buckets and output.
Frequently asked questions
Why must the per-digit pass be stable?
Stability is the entire mechanism. The work done on earlier digits survives only because a later pass never reorders elements that share the current digit. Swap in an unstable pass and the algorithm produces nonsense.
Why start from the least significant digit?
Least-significant-digit order lets a single sequence of passes handle the whole array with no recursion and no bookkeeping. Starting from the most significant digit also works but requires recursing into each bucket separately, since groups become independent subproblems.
Is a larger base faster?
Up to a point. Base 256 needs a quarter of the passes that base 10 does for a 32-bit key, at the cost of 256 buckets. Push the base higher and the bucket sweep plus cache pressure start to cost more than the passes you saved.