Loading...
Counting Sort is a non-comparison sort for integers over a bounded range. It tallies how many times each value appears, then writes the values back in order. It runs in O(n + k) time where k is the value range, beating comparison sorts when k is small relative to n.
Counts occurrences of each value, then places them in order.
| Average case | O(n + k) |
| Worst case | O(n + k) |
| Space | O(n + k) |
| Stable | Yes |
Complexities are for the reference implementation shown; constant factors and cache behavior vary by language.
Idiomatic, copy-paste implementations. Pick your language:
Python
def counting_sort(arr):
if not arr:
return arr
lo, hi = min(arr), max(arr)
counts = [0] * (hi - lo + 1)
for x in arr:
counts[x - lo] += 1
i = 0
for value, c in enumerate(counts):
for _ in range(c):
arr[i] = value + lo
i += 1
return arrSorting [2, 5, 2, 1] step by step:
The control flow of the algorithm as a diagram: