Counting Sort
Don't compare — count. Tally each key, compute positions with prefix sums, and place every element exactly once.
Hands on Interactive visualization
Implementation Code
// Stable counting sort; supports negatives via a min offset.
export function countingSort(a: number[]): number[] {
if (a.length === 0) return a;
const lo = Math.min(...a);
const hi = Math.max(...a);
const counts = new Array<number>(hi - lo + 1).fill(0); // k counters
for (const v of a) counts[v - lo]++;
// Prefix sums: counts[d] = index just past key d's final block.
for (let i = 1; i < counts.length; i++) counts[i] += counts[i - 1];
const out = new Array<number>(a.length);
// Reverse scan keeps equal keys in original order (stability).
for (let i = a.length - 1; i >= 0; i--) {
out[--counts[a[i] - lo]] = a[i];
}
return out;
}Big-O Complexity
k is the key range (max - min + 1). If k grows much faster than n — sparse keys — both time and memory are dominated by k.
In production When to use
Sorting by small fixed-domain keys — status codes, ages, enum ordinals, single bytes — in strictly linear time. Also the standard stable subroutine inside each radix sort pass.
Bucketing histogram-style workloads: ordering requests by HTTP status class, log lines by severity level, or events by hour-of-day, where the key domain is tiny and known in advance.
Sorting 8-bit values is a classic: 256 counters sort a whole image's pixels by intensity in one pass — histogram equalization does exactly this tally.
DNA data has a 4-letter alphabet; counting-based passes underpin suffix-array construction and k-mer bucketing at genome scale.
The proof that the O(n log n) lower bound only binds comparison sorts — with key knowledge, sorting is linear. Also the basis of O(n) problems like sorting an array of 0s, 1s and 2s.
Trade-offs Strengths & weaknesses
- Linear O(n + k) time — beats every comparison sort when k = O(n).
- Stable in its prefix-sum form, which is why radix sort can be built on it.
- No comparisons, no branches on data values in the hot loops — very fast constants.
- Deterministic performance: identical cost regardless of input order.
- Simple to reason about and verify; two passes plus a prefix sum.
- Memory and time explode with key range: sorting a few 64-bit values is impossible directly.
- Only sorts integer-like keys; arbitrary comparables need a comparison sort.
- Not in-place: needs a count array of size k plus an output array of size n.
- Not adaptive and not online — the full key range must be known or scanned first.
- Naive versions silently break on negative keys.
Intuition Mental model
Tallying ballots by candidate
An election count never compares ballots with each other. Each ballot bumps a per-candidate tally, and the final ordering is read straight off the tally board.
- Set up one tally box per possible candidate (one counter per key value).
- Walk the ballots once, incrementing the matching tally — no ballot ever looks at another ballot.
- Running totals (prefix sums) tell you where each candidate's block starts in the final ordering.
- Walk the ballots again — from the back, to keep equal ballots in received order — placing each directly into its reserved slot.
- Two linear walks, zero comparisons: that is how it sidesteps the n log n bound.
Prep Interview questions
Counting sort beats the O(n log n) lower bound — how is that possible?
Why must the placement pass iterate the input in reverse to be stable?
How do you handle negative numbers in counting sort?
When would you pick counting sort over quicksort for integers?
How does counting sort relate to radix sort?
Watch out Common bugs
counts[v] with v < 0 crashes (or wraps in C). Normalize with an offset: allocate max - min + 1 counters and index counts[v - min].
The classic off-by-one: a key equal to max needs slot counts[max], so the array must have max - min + 1 entries, not max - min.
Scanning the input left-to-right while decrementing prefix sums reverses each block of equal keys. Fine for bare ints, silently wrong for records — and fatal when used inside radix sort.
Allocating the count array from unvalidated max values lets one outlier (or attacker) request gigabytes. Validate the range or fall back to a comparison sort past a threshold.
One screen Cheat sheet
Histogram the keys, prefix-sum for positions, place in reverse for stability.
- Not comparison-based — that is how it goes sub-n-log-n.
- k = key range; only viable when k is around O(n) or a fixed constant.
- Prefix-sum + reverse-scan variant is stable; the simple overwrite variant is not.
- Offset by min to support negatives; size the counts array max - min + 1.
- The stable per-digit subroutine inside radix sort.