Counting Sort

Counting sort is a non-comparison sort for integers in a small range [0, k). It tallies how often each value appears, computes a prefix sum to get final positions, then writes each element directly into place. Linear in n+k.

Complexity

How it works

Walk the input building count[v] = number of times v appears. Convert to a prefix sum so count[v] is the index where the last occurrence of v should go. Walk the input in reverse, placing each element at count[v]−1 and decrementing — this preserves stability.

Python implementation

def counting_sort(arr):
    """Counting sort for non-negative integers."""
    if not arr:
        return arr
    k = max(arr) + 1
    count = [0] * k
    for x in arr:
        count[x] += 1
    for i in range(1, k):
        count[i] += count[i - 1]
    out = [0] * len(arr)
    for x in reversed(arr):
        count[x] -= 1
        out[count[x]] = x
    return out


print(counting_sort([4, 2, 2, 8, 3, 3, 1]))  # [1, 2, 2, 3, 3, 4, 8]

Trade-offs

• O(n+k) — linear when k = O(n).
• Stable; the workhorse pass inside radix sort.
• Useless when k >> n (e.g. sorting 10 ints in [0, 10⁹) wastes 10⁹ counter slots).
• Integer (or integer-mappable) keys only.

← Back to Algorithms