Counting sort

Every sort so far compares two items at a time, and a sort that only compares can't do better than O(n log n) in general: there are too many possible orders to tell apart with fewer comparisons. But when the values are small whole numbers, you don't need to compare them at all. You can count them.

Counting instead of comparing

Counting sort sorts whole numbers from 0 up to some largest value, k. It makes a list of k + 1 counters, one for each possible value, goes through the values once and adds one to each value's counter, and then writes each value out as many times as it was counted:

rolls = [3, 6, 1, 3, 5, 6, 3, 2]
counts = [0] * 7
for roll in rolls:
    counts[roll] += 1
print(counts)

result = []
for value in range(7):
    result += [value] * counts[value]
print(result)

[0, 1, 1, 3, 0, 1, 2]
[1, 2, 3, 3, 3, 5, 6, 6]

A die shows 1 to 6, so 7 counters cover the values 0 to 6 (counter 0 stays at 0). The value is the index of its own counter, so counting one value is O(1). [value] * counts[value] is a list of the value repeated: [3] * 3 is [3, 3, 3].

What it costs

Counting goes through the n values once, O(n). Writing them out goes through the k + 1 counters and adds the n values, O(n + k). So counting sort is O(n + k) in time, and needs O(k) memory for the counters, besides the result.

That beats the O(n log n) of comparison sorts when the range k is small next to the number of values n: a million exam scores from 0 to 100, ages, star ratings, dice. Python's own sorted runs in C and is hard to beat with Python code, yet on a million scores from 0 to 100, counting sort in plain Python is even faster.

It's a poor fit when the range is huge. Ten values up to a billion would need a billion counters: far more memory and time than sorting ten values. And it works only for whole numbers, or things you can number.

Values that don't start at 0 are shifted. For temperatures from -20 to 40, counter 0 is for -20, so the temperature t has the counter t + 20, and 61 counters cover the range. min(values) and max(values) find the range in O(n).

A tempting slow way is to count each possible value with values.count(value). Each call goes through the whole list, so that's O(n·k): for 200,000 values from 0 to 100,000, 20 billion comparisons.

Sorting records by a small number

Often the things you sort are records, like tuples or objects, and the small number is one part of each: tasks by priority, reviews by stars. The records have to stay whole, so instead of counters, use buckets: one list for each value. Put each record in the bucket of its number, then join the buckets in order:

tasks = [("email", 2), ("deploy", 0), ("lunch", 3), ("backup", 0), ("review", 2)]
buckets = [[] for _ in range(4)]
for task in tasks:
    buckets[task[1]].append(task)
print(buckets)

result = []
for bucket in buckets:
    result += bucket
print(result)

[[('deploy', 0), ('backup', 0)], [], [('email', 2), ('review', 2)], [('lunch', 3)]]
[('deploy', 0), ('backup', 0), ('email', 2), ('review', 2), ('lunch', 3)]

[[] for _ in range(4)] makes four separate empty lists (_ is the usual name for a loop variable you don't use). The records in a bucket stay in the order they came in, so this sort is stable: deploy before backup, email before review. It's O(n + k) again.