Every sort so far works by comparing two elements and asking "which is bigger?". It has been proved that any sort that learns about the order only by comparing needs at least about n \log_2 n comparisons in the worst case. Chapter 4.10 gives the short proof. The idea is that there are n! possible orders of n items, and each yes-or-no comparison can at best cut the possibilities in half.
The way around it is to not compare at all. If the values are small whole numbers, a value can be used directly as a position in a list. That tells you where it goes without comparing it to anything.
Count how many times each value appears. Then write the values back out in order, each repeated by its count. This is the same counting idea as the 0s, 1s and 2s in 4.0.20, stretched to any small range.
python
def counting_sort_simple(nums: list[int], max_value: int) -> list[int]: counts = [0] * (max_value + 1) # (1) for x in nums: counts[x] += 1 # (2) out = [] for value, c in enumerate(counts): # (3) out.extend([value] * c) return outprint(counting_sort_simple([4, 2, 2, 8, 3, 3, 1], 8)) # → [1, 2, 2, 3, 3, 4, 8]
(1) One counter for every possible value, from 0 to max_value.
(2) The value itself is the position of its counter. No comparison happens.
(3) Walk the counters in order, 0 upward, and write each value as many times as it was counted.
For the exam marks: 101 counters, one pass to count a million marks, one pass over 101 counters to write them out. About two million simple steps, instead of the roughly 20 million comparisons a comparison sort would need.
The simple version rebuilds the values from the counts. That is fine for plain numbers. But usually you sort records by a key: students by mark, orders by priority. Rebuilding would throw away everything except the key. We need to move the actual records, and keep records with equal keys in their original order. That means a stable sort.
The trick turns the counts into positions.
Count each key, as before.
Change each count into the number of records with a smaller or equal key. This is a running total, the prefix sum from 4.0.22. Now counts[k] says where the last record with key k should end: just before position counts[k].
Walk the input from right to left. Place each record at position counts[key] - 1, then reduce counts[key] by one.
Why from right to left? Among records with the same key, the rightmost one is placed first, into the last slot for that key. The next one to its left goes into the slot before it. So equal keys end up in the same order they started in.
python
def counting_sort(items: list, key, max_key: int) -> list: counts = [0] * (max_key + 1) for it in items: counts[key(it)] += 1 # (1) for k in range(1, max_key + 1): counts[k] += counts[k - 1] # (2) out = [None] * len(items) for it in reversed(items): # (3) k = key(it) counts[k] -= 1 out[counts[k]] = it # (4) return outstudents = [("Asha", 72), ("Ben", 65), ("Chen", 72), ("Dev", 90), ("Esi", 65)]print(counting_sort(students, key=lambda s: s[1], max_key=100))# → [('Ben', 65), ('Esi', 65), ('Asha', 72), ('Chen', 72), ('Dev', 90)]
(1) Count each key.
(2) Running total. Now counts[k] is how many records have a key of k or less.
(3) Walk from the end, so equal keys stay in order.
(4) Reduce the count first, then use it as the position. The last record with key 72 goes into the last slot reserved for 72.
Ben and Esi both have 65, and Ben came first in the input. Ben is still first in the output. The same holds for Asha and Chen. That is stability.
Trace of step (2) for the marks 65, 72 and 90: after counting, counts[65] = 2, counts[72] = 2 and counts[90] = 1. After the running total, counts[65] = 2, counts[72] = 4 and counts[90] = 5. So the 65s go in positions 0 and 1, the 72s in 2 and 3, and the 90 in position 4.
Negative values. Shift every key by the smallest value, so the smallest becomes 0. For keys from -50 to 50, use key(it) + 50, and make 101 counters.
Two passes over the n items and one pass over the k possible key values. That is O(n + k) time and O(n + k) memory.
The catch is k. Counting sort is only fast when the range of keys is small compared with n. Sorting ten numbers that range up to a billion would need a billion counters. That is far slower than any comparison sort.
Phone numbers have 10 digits. As keys they range up to 10^{10}. That is far too many counters. But each single digit only ranges from 0 to 9. Radix sort uses counting sort on one digit at a time.
Radix sort is older than computers. Herman Hollerith built machines to count the 1890 United States census using punched cards. His card sorters, and the IBM machines that followed, sorted a stack of cards by one column at a time, dropping each card into one of ten bins. An operator ran the stack through the machine once per digit. Starting with the last digit, then the second-to-last, and so on.
Sort by the ones digit first. Then sort by the tens digit, with a stable sort. Then the hundreds.
After the tens pass, numbers with different tens digits are in the right order. And numbers with the same tens digit? The stable sort kept them in the order the ones pass left them, which is sorted by the ones digit. So after the tens pass, the list is sorted by its last two digits. Each pass adds one more correct digit. After the last pass, the whole list is sorted.
This only works if each pass is stable. An unstable pass would scramble the order the earlier passes built.
Watch it on [170, 45, 75, 90, 802, 24, 2, 66]:
pass
sort by
list after
1
ones digit
170 90 802 2 24 45 75 66
2
tens digit
802 2 24 45 66 170 75 90
3
hundreds digit
2 24 45 66 75 90 170 802
Look at pass 2. 802 and 2 both have tens digit 0. They stay in the order pass 1 gave them, 802 before 2. Then pass 3 sorts by hundreds: 2 has hundreds digit 0, and 802 has 8, so they swap into the right order.
def radix_sort(nums: list[int]) -> list[int]: if not nums: return nums place = 1 # (1) biggest = max(nums) while biggest // place > 0: # (2) nums = counting_sort(nums, key=lambda x: (x // place) % 10, max_key=9) # (3) place *= 10 return numsprint(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))# → [2, 24, 45, 66, 75, 90, 170, 802]
(1)place is 1 for the ones digit, 10 for the tens, 100 for the hundreds.
(2) Keep going while the biggest number still has a digit at this place. 802 has three digits, so there are three passes.
(3)(x // place) % 10 picks out one digit. For x = 802 and place = 10, 802 // 10 is 80, and 80 % 10 is 0, the tens digit. This reuses the stable counting_sort from above with only 10 counters.
This version handles non-negative whole numbers. For negatives, sort them separately and put them first in reversed order, or add an offset.
d passes, one per digit, each O(n + 10). Total O(d \times n). For numbers with a fixed number of digits, d is a constant, so radix sort is O(n). For 10-digit phone numbers, 10 passes over the list.
It uses O(n) extra memory for each pass's output list. It is stable, because every pass is.
Real implementations often use base 256, one byte at a time, instead of base 10. That means fewer passes with more counters.
Neither can sort by an arbitrary rule. To sort names by a custom alphabet, or by "most recently active", you need comparisons again. That is why real libraries use comparison sorts by default.
There is a third sort that does not compare, called bucket sort. It works on values spread evenly over a range, like decimals between 0 and 1. It drops them into buckets by size, then sorts each small bucket. It averages O(n) when the values really are spread out evenly.
These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.
"Can you sort faster than O(n \log n)?" Yes, but only by not comparing values. Counting sort and radix sort use the values themselves as positions. Any sort that compares values needs about n \log n steps.
"Why must radix sort use a stable sort for each digit?" Each pass must keep the order that the earlier passes set up. An unstable pass would mix it up again.
"Why start from the last digit?" The first digit matters most, so it must be sorted last and have the final say. The earlier passes then only break ties.
"When is counting sort a bad idea?" When the values cover a huge range, like 10 numbers up to a billion. You would need a billion counters.
One thing to volunteer: "Counting sort is fast only because it knows the values are small whole numbers. A comparison sort knows nothing about the values, which is why it can sort anything."
Next:4.0.31 Tower of Hanoi. The puzzle that teaches recursion better than any other.