Counting Sort

Non-comparison · Stable · O(n + k)

1:00

A non-comparison, stable sorting algorithm that tallies value frequencies, prefix-sums them into positions, and places elements in O(n + k) time.

By the end, you can

Explain why counting sort is not bounded by Ω(n log n) while merge sort is.
State the single essential requirement for counting sort to be correct and efficient.
Execute Phase 1 (counting) by hand and verify that counts sum to n.
Execute Phase 2 (prefix sum) by hand and interpret what each cumulative count means.
Execute Phase 3 (reverse placement) by hand, tracing the decrement-then-place logic for each element.
Explain why scanning right to left during placement preserves stability, and what happens if you scan left to right.
State the time and space complexity as O(n + k) and identify when that is effectively linear.
Decide whether counting sort is the right tool given n and k, and adjust for negative or shifted key ranges.

Up next in Searching & Sorting