Counting, Bucket & Radix Sort
In short: every sort in section 3 decided order by comparing two
items. Counting sort never compares anything — it counts how many times each
value occurs, turns those counts into positions with a running total, then
places each item straight into its final slot. That makes it O(n + k),
where k is the range of values, beating any comparison sort's O(n log n)
floor. But it only works on a small range of non-negative integers. Radix
sort lifts that limit by running a stable counting sort once per digit,
from the ones place up, so it can sort numbers of any size in O(d·n), where
d is the digit count. Both are stable — and they have to be, or radix
sort's later digit-passes would undo the sorting the earlier passes did.
Sort record IDs without comparing them
Quarry ingests a batch of small non-negative record IDs overnight and needs them sorted before the morning read. Counting sort never asks "is this one bigger than that one" — it only counts:
The prefix-summed counts array turns "how many 2s are there" into "how many
items belong at or before a 2" — exactly the final index each item needs,
counting from the back so that the last equal item lands in the
highest open slot, leaving earlier arrivals the lower ones. Watch the
output array fill in, one placement at a time:
Scanning the input backward and placing straight into the final slot is what keeps equal values in their original order.
The last input value is 2 (index 5). Its running count says "one belongs at position 3". 6 cells. At index 3.
Sort record IDs with six-digit numbers
Counting sort's counts array would need one slot per possible ID — useless once IDs run into the millions. Radix sort keeps counting sort's O(n) shape by running it on one digit at a time, least significant first, so the counts array only ever needs 10 slots:
Watch one digit pass distribute five two-digit IDs into 10 buckets by their ones digit, then read the buckets back top to bottom:
Each bucket is a row, keyed by the digit in focus. Reading the rows back in order 0 to 9 sorts by that digit — and keeps ties in the order they arrived, because a bucket is filled left to right.
29 ends in 9, so it goes into row 9, the first open slot. 10 by 2 table. At row 9, column 0 — value 29. 1 of 20 cells filled.
The tens pass runs next on [43, 34, 8, 29, 19], this time keying on the
digit that was already the tiebreaker — and because both passes are stable,
the ones-digit order survives inside every tens-digit group.
Why "stable" is not optional here
A sort being stable is a nice-to-have almost everywhere else. For radix sort it is the entire algorithm. Sort unstably on the ones digit, and the tens pass has no way to recover which of two same-tens-digit numbers came first:
def unstable_counting_sort_by_digit(nums, exp):
buckets = [[] for _ in range(10)]
for x in sorted(nums, reverse=True): # sorting first "for speed" — breaks arrival order
buckets[(x // exp) % 10].append(x)
return [x for bucket in buckets for x in bucket]
step1 = unstable_counting_sort_by_digit([23, 21, 45], 1) # sort by ones digit
print(step1)def unstable_counting_sort_by_digit(nums, exp):
buckets = [[] for _ in range(10)]
for x in sorted(nums, reverse=True):
buckets[(x // exp) % 10].append(x)
return [x for bucket in buckets for x in bucket]
after_ones = unstable_counting_sort_by_digit([23, 21, 45, 25], 1)
after_tens = unstable_counting_sort_by_digit(after_ones, 10)
print(after_tens)Quick practice
counts = [0, 0, 0, 0]
for x in [2, 3, 0, 2, 3, 2]:
counts[x] += 1
for i in range(1, 4):
counts[i] += counts[i - 1]
print(counts)This sorts every digit backward. Fix the one word that reverses the read-back order.
🎯 Your turn
Build radix_sort(nums): return a new list with nums sorted ascending.
nums are non-negative integers. Use LSD radix sort — a stable counting-sort
pass for each digit, from the ones place up — not sorted().
radix_sort([170, 45, 75, 90, 802, 24, 2, 66])→[2, 24, 45, 66, 75, 90, 170, 802]radix_sort([])→[]
Hint: exp starts at 1 and multiplies by 10 each pass, while
max(nums) // exp > 0. (x // exp) % 10 reads the digit currently in
focus. Scan out in its current order when filling the 10 buckets — that's
what keeps the sort stable.
Press ▶ Run, try the Live App chips, then ✓ Check.