Counting sort

Why it costs this much

One pass counts each value, then one pass over the k possible values writes the output.

Code

def counting_sort(nums, k):        # values are 0..k-1
    counts = [0] * k
    for x in nums:                 # O(n)
        counts[x] += 1
    out = []
    for v in range(k):             # O(k), plus n appends in total
        out.extend([v] * counts[v])
    return out

Common pitfalls

If k is far larger than n, such as a few numbers up to a billion, it is slower than a comparison sort. This version sorts bare integers. To sort records by key and keep them stable, use the prefix-sum version.

Operation by operation

Counting sort. Integer keys in a known range of size k. Stable in the standard version. If k is much larger than n, this is slower than a comparison sort.