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.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(n+k) |
Θ(n+k) |
O(n+k) |
O(k) |
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.
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]The trace above sorts seven keys whose maximum is 8, so k = 9 counters are allocated. The first pass is a pure histogram: value 2 and value 3 each appear twice, so their counters hold 2. The second pass turns the histogram into a running total. After it, prefix[v] answers the question "how many keys are less than or equal to v", which is exactly one past the index of the last copy of v in the sorted output. For example prefix[3] = 5, so the two 3s occupy indices 3 and 4.
The third pass walks the input from right to left. Each key looks up its counter, decrements it, and drops into that slot. Nothing is ever compared with anything else, which is why the Ω(n log n) lower bound for comparison sorts does not apply: that bound counts comparisons, and counting sort performs none.
Stability means records with equal keys keep their original relative order. It does not matter when sorting bare integers, but it is essential when the key is one field of a larger record, and it is the property radix sort depends on. Because the prefix sum points one past the last slot for each value, filling from the back of the input puts the rightmost equal record into the rightmost slot. Walking forward would also produce a sorted result, but equal keys would come out reversed. An equivalent formulation shifts the prefix sum by one (an exclusive scan giving the first slot) and walks forward; both are correct as long as the direction matches the scan type.
The common practical use is ordering records by a bounded integer attribute such as an age, a grade, an HTTP status class, or a priority level. The version below takes a key function, handles negative values by offsetting with the minimum, and returns a new list.
def counting_sort_by(records, key):
if not records:
return []
keys = [key(r) for r in records]
lo, hi = min(keys), max(keys)
count = [0] * (hi - lo + 1)
for k in keys:
count[k - lo] += 1
for i in range(1, len(count)):
count[i] += count[i - 1]
out = [None] * len(records)
for r, k in zip(reversed(records), reversed(keys)):
count[k - lo] -= 1
out[count[k - lo]] = r
return out
people = [("ana", 31), ("bo", 25), ("cy", 31), ("di", -1), ("ed", 25)]
print(counting_sort_by(people, key=lambda p: p[1]))
# [('di', -1), ('bo', 25), ('ed', 25), ('ana', 31), ('cy', 31)]Note that bo still precedes ed and ana still precedes cy, confirming stability. The memory cost is the count array of size hi - lo + 1 plus the output array of size n.
| Situation | Better choice | Reason |
|---|---|---|
| Integer keys, range k comparable to n | Counting sort | True O(n+k), stable, simple |
| Wide integer keys (32/64-bit) | Radix sort | Runs counting sort per digit, so k stays small |
| Uniformly distributed floats | Bucket sort | Buckets by value range, then sorts small buckets |
| Arbitrary comparable objects | Timsort (Python sorted) | No key range assumptions; O(n log n) |
If you only need counts per value (a histogram) and not a sorted array, stop after the first pass; collections.Counter or numpy.bincount do exactly that.
max - min, not to n. One outlier such as 109 in a list of small numbers makes the algorithm allocate a billion counters.sorted, implemented in C, is usually faster than a pure-Python counting sort even when the asymptotics favour the latter.