Counting Sort
Count occurrences of each value, then reconstruct sorted output.
How it works
Counting Sort achieves O(n + k) time complexity — faster than any comparison-based sort — by exploiting the fact that the input values are bounded integers in a known range [0, k]. Instead of comparing elements against each other, it tallies how many times each distinct value appears in a count array, then uses a prefix-sum pass to convert those counts into correct sorted positions.
The algorithm runs in three clean phases. First, it iterates the input and increments count[value] for each element. Second, it converts the count array into a cumulative prefix sum so that count[v] now holds the number of elements ≤ v, which equals the last valid output index for value v. Third, it scans the input right-to-left and places each element at count[value]-1, decrementing the counter afterwards — this right-to-left traversal is what makes the sort stable.
Counting Sort is not in-place (it requires O(k) auxiliary space for the count array and O(n) for the output buffer) and is only practical when the key range k is comparable in size to n. For wide integer domains like 32-bit values, Radix Sort is preferred because it applies counting sort digit-by-digit on a much smaller k.
Complexity
Visualizer
Where it's used in the real world
Network packet schedulers
Sorting packets by priority class (0–63)Priority values are small bounded integers. Counting sort empties the O(k) priority buckets in O(n + k) time without any per-packet comparisons, giving deterministic low-latency scheduling on hardware with fixed queue depths.
Bioinformatics / DNA analysis
Counting and sorting character frequencies in DNA sequencesDNA alphabets are tiny (A, C, G, T — only 4 symbols). Counting sort processes gigabyte-scale sequences in a single linear pass, orders of magnitude faster than comparison sorts for tasks like k-mer frequency tables.
Census and demographic data processing
Age-based sorting for population statisticsHuman ages span a bounded range (0–120). Sorting hundreds of millions of records by age in O(n) is practical with counting sort, and the stability guarantee preserves original record order within the same age cohort — important for reproducible statistical outputs.
Implementation
function countingSort(arr: number[]): number[] {
const max = Math.max(...arr);
const count = new Array<number>(max + 1).fill(0);
const output = new Array<number>(arr.length);
// Phase 1: tally occurrences
for (const val of arr) {
count[val]++;
}
// Phase 2: prefix sum → sorted positions
for (let i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// Phase 3: place elements right-to-left (stable)
for (let i = arr.length - 1; i >= 0; i--) {
output[--count[arr[i]]] = arr[i];
}
return output;
}
// Usage
console.log(countingSort([4, 2, 2, 8, 3, 3, 1]));
// [1, 2, 2, 3, 3, 4, 8]