Radix Sort
DSA · Sorting Algorithms
Theory
Radix sort sorts integers digit by digit, from the least significant digit to the most significant, using a stable sort (usually counting or bucket sort) for each digit. After processing every digit position the numbers are fully sorted. Its time is O(d × (n + b)), where d is the number of digits and b the base (10 for decimal).
Why we use it
It sorts large lists of fixed-length integers or strings in linear time with respect to n.
When to use it
Use it for phone numbers, IDs, dates as integers, or fixed-length strings, when d is small.
How it works
- Find the maximum number of digits d
- Start with the least significant digit
- Stable-sort all numbers by this digit (counting sort)
- More digits left? Yes: Move to the next digit, repeat. No: Array is sorted.
- Done
Syntax
for each digit position (ones, tens, hundreds...):
distribute numbers into buckets 0-9 by that digit
collect buckets in order
Time: O(d·(n+b)) Space: O(n+b) StableExample
def radix_sort(arr):
exp = 1
while max(arr) // exp > 0:
buckets = [[] for _ in range(10)]
for num in arr:
buckets[(num // exp) % 10].append(num)
arr = [n for b in buckets for n in b]
print("After digit", exp, ":", arr)
exp *= 10
return arr
radix_sort([170, 45, 75, 90, 802, 24, 2, 66])Key points
- Sorts digit by digit
- Each pass must be stable
- Linear in n for fixed digit counts
- Works for non-negative integers (extra handling for negatives)