Counting Sort
Sorting without comparing.
Every sort so far compares items. Comparison sorts can never beat O of N log N. But if your values are small whole numbers, like exam marks from zero to a hundred, you can sort without comparing at all, by counting.

- Comparison sorts: O(n log n) at best
- Small whole numbers?
- Sort by counting
Count, then rebuild
Make one counter for every possible value. Go through the data once, and add one to the counter for each value. Then walk through the counters in order, and write each value out as many times as it was counted. Run it.
def counting_sort(nums, max_value):
counts = [0] * (max_value + 1)
for n in nums:
counts[n] += 1
result = []
for value, count in enumerate(counts):
result.extend([value] * count)
return result
print(counting_sort([4, 1, 3, 4, 0, 2, 1, 4], 4))[0, 1, 1, 2, 3, 4, 4, 4]
When counting sort wins
Counting sort is O of N plus K, where K is the range of values. For marks out of a hundred, or ages, that's effectively O of N, faster than any comparison sort. But if the values range up to a billion, you'd need a billion counters, so it's useless there.
| key | value |
|---|---|
| Time | O(n + k) |
| k | the range of values |
| Great for | marks, ages, small ranges |
| Bad for | huge ranges, decimals, text |
Summary
Counting sort counts each value, and rebuilds the list, in O of N plus K. It only works for small ranges of whole numbers. Next, a practice problem where sorting is the key step.
Key takeaways- Count each value
- Rebuild in order
- O(n + k)