The Story That Explains Radix Sort
He looks only at the last digit of every postcode and drops each letter into the matching pigeonhole. Then he scoops the holes back up in order 0→9, and repeats — this time on the second-to-last digit, then the third, and so on. After five quick passes, with zero comparisons between any two postcodes, the entire stack is perfectly sorted.
That clerk just performed Radix Sort.
Radix Sort is a non-comparative integer sorting algorithm. Instead of asking “is A bigger than B?”, it sorts numbers digit by digit, using a stable bucketing pass for each digit position. Because it never compares whole keys, it sidesteps the famous O(n log n) lower bound that limits comparison sorts.
If keys are built from a small fixed alphabet of symbols (digits 0–9, or bytes 0–255), you can sort them by repeatedly bucketing on one symbol position at a time. Do it from the least significant digit (LSD) to the most significant, keep each pass stable, and the array falls into perfect order.
The Two Ingredients of Radix Sort
Radix Sort is really just two simple ideas working together. Neither alone sorts anything — together they are unstoppable.
When the tens-digit pass groups numbers, ties (same tens digit) must keep the order the ones pass already gave them. An unstable bucket pass would scramble that earlier work and the final result would be wrong. Stability is what chains the passes together.
How It Works — Step by Step
Hands-On — Watch Each Line Do Its Job
This is the heart of the tutorial. Press Step (or Auto) and watch: the highlighted code line is the one currently executing, the caption explains exactly what that line is doing, and the array & buckets animate the effect of that line in real time.
Watch line 7 extract the digit, line 8 drop the number into a green bucket, and line 9 scoop them all back in order. Two numbers with the same current digit always land in the same bucket in the order they arrived — that is stability happening before your eyes.
The Same Run, as a Table
Here is exactly what the animation does, frozen into three passes for
[329, 457, 657, 839, 436, 720, 355].
| Pass | Sort On | Array After This Pass |
|---|---|---|
| Start | — | 329, 457, 657, 839, 436, 720, 355 |
| Pass 1 | Ones digit | 720, 355, 436, 457, 657, 329, 839 |
| Pass 2 | Tens digit | 720, 329, 436, 839, 355, 457, 657 |
| Pass 3 | Hundreds digit | 329, 355, 436, 457, 657, 720, 839 |
After Pass 1 the numbers are ordered by their last digit only. After Pass 2 they are ordered by the last two digits. After Pass 3, by all three — which is the full order. Each pass refines the previous one because every pass is stable.
Full Python Implementation
LSD Radix Sort (the version animated above)
def radix_sort(arr):
# Edge case: empty list is already sorted
if not arr:
return arr
# 1. Largest value decides how many digit-passes we need
max_val = max(arr)
place = 1 # start at the ones digit
# 2. One stable pass per digit, LSD -> MSD
while max_val // place > 0:
buckets = [[] for _ in range(10)] # 10 empty buckets, digits 0-9
# 3. Distribute every number by its current digit
for num in arr:
digit = (num // place) % 10 # peel off one digit
buckets[digit].append(num) # append keeps it stable
# 4. Collect buckets 0->9 back into the array
arr = [num for bucket in buckets for num in bucket]
place *= 10 # advance to the next digit
return arr
# ── Demo ──────────────────────────────────────────────
data = [329, 457, 657, 839, 436, 720, 355]
print("Before:", data)
print("After: ", radix_sort(data))Handling Negative Numbers (a common gotcha)
Plain radix sort only works on non-negative integers. The simplest robust fix: split the array, sort the absolute values of the negatives, reverse and negate them, then concatenate.
def radix_sort_signed(arr):
neg = [-x for x in arr if x < 0] # magnitudes of negatives
pos = [x for x in arr if x >= 0]
neg = radix_sort(neg) # sort magnitudes ascending
pos = radix_sort(pos)
# negatives go first, reversed and re-negated
return [-x for x in reversed(neg)] + posLSD vs MSD — Two Flavours
| Property | Behaviour |
|---|---|
| Direction | Ones → highest digit |
| Passes | Always d (fixed) |
| Stability | Stable, simple |
| Best for | Fixed-width integers |
| Recursion | None — flat loop |
| Property | Behaviour |
|---|---|
| Direction | Highest digit → ones |
| Passes | Can stop early per group |
| Stability | Needs care to stay stable |
| Best for | Strings, variable length |
| Recursion | Recursive on sub-buckets |
The animated version above is LSD — the most common and easiest to reason about. MSD shines for sorting strings (like a dictionary), because it can finish ordering a group as soon as a prefix is decided, without touching the rest of every word.
Complexity & The Cost of Speed
With n items, d digits per key, and a radix (base) of k
buckets, each pass is O(n + k) and there are d passes:
Time = O(d · (n + k))
Space = O(n + k)
When d and k are small constants, this collapses to a
near-linear O(n) — faster than any comparison sort.
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Radix Sort | O(n·k) | O(n·k) | O(n·k) | O(n+k) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
That O(n) hides a real cost. For huge keys, d grows; if d ≈ log n, radix sort is no better than quicksort. It also needs extra memory for buckets and works cleanly only on fixed-length, discrete keys (integers, fixed strings). It is a specialist, not a general-purpose replacement.
When To Use Radix Sort (and When Not To)
Benefits at a Glance
Golden Rules
append to buckets and read them
back in order. Swap in an unstable subroutine and every earlier pass is destroyed.
max(arr);
never hard-code the number of passes.