Counting Sort

Counting sort tallies how many of each key value occur, then places elements directly, sorting in linear time for a small key range.

Count, then place

Counting sort works when keys are integers in a small known range 0 to k. It first counts how many times each value occurs, then converts those counts into starting positions, and finally scans the input placing each element at the position its key dictates. No two elements are ever compared.

Linear when the range is small

With n elements and key range k, the algorithm does O(n + k) work: one pass to count, one to accumulate positions, and one to place. When k is O(n) this is linear time, faster than any comparison sort. When k is much larger than n, the count array wastes memory and the method loses its advantage.

• Time: O(n + k)
• Extra space: O(n + k)
• Stable: yes, when placement scans the input in reverse
• Requires integer keys in a bounded range

def counting_sort(a, k):
    count = [0]*(k+1)
    for x in a: count[x] += 1
    for i in range(1, k+1): count[i] += count[i-1]
    out = [0]*len(a)
    for x in reversed(a):
        count[x] -= 1
        out[count[x]] = x
    return out

Why reverse-order placement gives stability

After the counts are turned into ending positions, scanning the input from right to left and placing each element just before the previous one of its key preserves the original order of equal keys. Scanning left to right instead would reverse ties. This stability is not a nicety: it is exactly what radix sort relies on to combine digit passes correctly.

Its role as a building block

Counting sort's stability makes it the per-digit engine inside radix sort: radix sort applies counting sort to one digit at a time to handle keys with a large range using a small base. On its own, counting sort is ideal for sorting exam scores, ages, histogram bins, or any bounded-integer attribute in linear time, and it also produces a frequency histogram as a useful side product.