Counting Sort

The Idea

If the values come from a small known range, count how many times each one appears, then read the counts back out in order. That is O(n + k), faster than any comparison sort, but only for that shape of data.

Real-World Example

Tallying T-shirt sizes for a conference. Nobody ever compares two shirts. You count how many S, M, L, and XL were ordered, then pack the boxes in size order straight from the tally sheet.

The Code

def counting_sort(nums, max_value):
    counts = [0] * (max_value + 1)
    for x in nums:
        counts[x] += 1              # tally each value
    out = []
    for value, times in enumerate(counts):
        out.extend([value] * times) # read the tallies in order
    return out

print(counting_sort([3, 1, 3, 0, 2], 3))   # [0, 1, 2, 3, 3]

nums = [2, 0, 2, 1]
counts = [0] * 3
for x in nums:
  counts[x] += 1
print(counts)