patternjavascriptTip
Counting sort is O(n+k) for bounded integer ranges — beats comparison sorts
Viewed 0 times
counting sortlinear sortradix sortinteger sortfrequency countbounded range
Problem
Comparison-based sorts are O(n log n) at best. When the input is integers in a known bounded range [0, k], a non-comparison sort can beat this lower bound entirely.
Solution
Counting sort: allocate a count array of size k+1. Increment count[x] for each x. Accumulate counts to get positions. Write elements into output array at their correct position. O(n+k) time and space. Stable when iterating the input in reverse during placement.
Why
Counting sort sidesteps the O(n log n) lower bound for comparison sorts by using values as indices. It exploits the bounded range assumption — not applicable when the range k >> n.
Gotchas
- If k is much larger than n (e.g., sorting 10 elements in range 0..10^9), counting sort is worse than merge sort — use radix sort instead
- For stability, iterate the input array in reverse during the placement pass
- Negative values need an offset: shift all values by |min| so range starts at 0
Code Snippets
Stable counting sort
// Counting sort for integers in [0, maxVal]
function countingSort(arr, maxVal) {
const count = new Array(maxVal + 1).fill(0);
for (const x of arr) count[x]++;
// Stable version: prefix sums + reverse placement
for (let i = 1; i <= maxVal; i++) count[i] += count[i-1];
const out = new Array(arr.length);
for (let i = arr.length - 1; i >= 0; i--)
out[--count[arr[i]]] = arr[i];
return out;
}Context
Sorting arrays of integers within a known small range (e.g., age, grades, month numbers)
Revisions (0)
No revisions yet.