A non-comparison sort! Counts occurrences of each value, then places elements using cumulative counts. No element comparisons needed.
Ready
Comparisons: 0 (always 0!)
Writes: 0
Phase: Idle
Complexity: O(n + k) time & space
How Counting Sort Works
Phase 1: Build a count array — for each value v, count[v]++. Phase 2: Compute cumulative sums — count[i] += count[i-1]. Phase 3: Place elements into output array using counts as indices.
No comparisons are ever made between elements! Works best when the range of values (k) is small relative to n.