Counting Sort
Skips comparisons entirely: tally how many times each value occurs, then rebuild the array in order. O(n + k) — unbeatable when the value range k is small.
- Category
- Sorting
- Time complexity
- O(n + k)
- Space complexity
- O(k) (Stated for the auxiliary count array only. Some texts write O(n + k) to also account for the output array — both conventions are common.)
Pseudocode
counting sort (no comparisons) counts[A[i]] += 1 walk counts in order write each value count times done
Reference implementation
counts = [0] * (k + 1)
for v in a: counts[v] += 1
out = []
for v, n in enumerate(counts):
out += [v] * n