Counting and radix sorting
Picture
Values [2,0,2,1] come from the tiny known range 0..2. Count each value directly.
Predict
Is counting sort efficient when keys range from 0 to one trillion?
Walk through the small example
Usually no. Key structure is stronger than arbitrary comparison, allowing direct buckets.
Mental model and complete Python solution
Comparison sorting learns order by asking pairwise questions. Counting sort already knows every possible bucket. Radix sort learns a long key in stable digit-sized layers.
What the function promises: Return nonnegative integers in sorted order. This counting implementation requires a configurable maximum key and rejects values outside it.
def counting_sort(values, maximum):
if maximum < 0 or any(type(v) is not int or not 0 <= v <= maximum for v in values):
raise ValueError("Value outside key range")
counts = [0] * (maximum + 1)
for value in values:
counts[value] += 1
return [value for value, count in enumerate(counts) for _ in range(count)]
assert counting_sort([2,0,2,1], 2) == [0,1,2,2]
assert counting_sort([], 0) == []Work and storage: O(n + K) time and O(K) auxiliary space for maximum key K.
When to recognize it: Key structure is stronger than arbitrary comparison, allowing direct buckets.
Check before applying it: Memory depends on the key range; radix requires a stable pass and careful signed-value handling.
Change one rule
Keys are signed 32-bit integers.
See what changes
Offset a manageable range, or use sign-aware radix passes; do not allocate billions of buckets.
Connect
Sorting: buy useful order: These algorithms exploit more than comparison order.
dictionaries: Frequencies are useful even when the key range is sparse.