What is counting sort and when can it beat O(n log n)?
Counting sort counts how many times each value appears in a small integer range, then rebuilds the array from those counts. It runs in O(n + k) time for values in 0..k, so it beats comparison sorts when k is small.
Explain it simply
Comparison sorts like merge sort cannot go below O(n log n) because they only compare pairs. Counting sort does not compare at all. It just tallies.
Think of counting how many students scored each mark from 0 to 10. You make eleven tally boxes, go through the papers once, then read the boxes in order: two 1s, one 2, and so on. That gives the sorted list.
It only works well when the range of values k is small compared with the number of items. Sorting a million numbers between 0 and 10^9 would waste memory.
Example
function countingSort(arr, maxValue) {
const counts = new Array(maxValue + 1).fill(0);
for (const x of arr) counts[x]++;
const result = [];
for (let v = 0; v <= maxValue; v++) {
for (let c = 0; c < counts[v]; c++) result.push(v);
}
return result;
}
console.log(countingSort([4, 2, 2, 8, 3, 3, 1], 8)); // Output: [1,2,2,3,3,4,8]Complexity
Time O(n + k), space O(k).
What to say in the interview
"Counting sort tallies each value in an array of size k plus one and then writes values out in order. Time is O(n + k) and space is O(k). It beats the O(n log n) comparison lower bound for small integer ranges, but it is a poor choice when k is huge or the data is not integers."
Common mistakes
- Using it for large or negative ranges without shifting values.
- Saying it breaks the comparison-sort lower bound. It does not compare, so the bound does not apply.