Counting Sort and Choosing a Sort

Sorting without comparing

If the values are small whole numbers – like marks from 0 to 100 – you don't need to compare at all. Just count how many of each value there are, then write them out in order:

def counting_sort(nums, max_value):
    count = [0] * (max_value + 1)
    for x in nums:
        count[x] += 1
    out = []
    for value in range(max_value + 1):
        out.extend([value] * count[value])
    return out

marks = [7, 3, 9, 3, 0, 7, 7, 10]
print(counting_sort(marks, 10))

Output

[0, 3, 3, 7, 7, 7, 9, 10]

Think of it like this: Sorting coins: you don't compare coins with each other – you drop each into the ₹1, ₹2, ₹5 or ₹10 pile, then stack the piles in order.

Time: O(n + k), where k is the range of values. That beats O(n log n) – but only when k is small.

Which sort should I use?

Remember: No sort that works by comparing items can beat O(n log n) in general. Counting sort is faster only because it doesn't compare.