Counting Sort

Counting Sort

Counting sort breaks the O(n log n) barrier by not using comparisons at all. Instead, it counts how many times each value appears, then uses those counts to reconstruct the sorted array. It's like tallying votes — count how many people voted for each candidate, then list the results in order.

This algorithm only works when the input consists of integers within a known range. If you're sorting ages (0-150), student IDs (1-1000), or letter grades (A-F mapped to 1-5), counting sort is blazing fast. But it can't sort arbitrary objects without a key extraction step.

How It Works

First, create a count array sized to the range of input values. Walk through the input and increment the corresponding count for each element. Then, reconstruct the sorted array by iterating through the count array and writing each value the appropriate number of times.

That's it — two passes through the data. The counting pass is O(n), and the reconstruction pass is O(k) where k is the range of values. Total time: O(n + k). If k is small relative to n, this absolutely crushes comparison sorts.

function countingSort(arr) {
  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);
  for (const num of arr) {
    count[num]++;
  }
  const sorted = [];
  for (let i = 0; i < count.length; i++) {
    while (count[i] > 0) {
      sorted.push(i);
      count[i]--;
    }
  }
  return sorted;
}
console.log(countingSort([4, 2, 2, 8, 3, 3, 1]));

Time Complexity

Time complexity is O(n + k) where n is the number of elements and k is the range of values. Space complexity is O(k) for the count array. When k is O(n) or smaller, counting sort is linear — that's O(n) vs O(n log n), which is a massive improvement for large datasets.

The catch is that k can be a problem. If you're sorting values from 0 to 1,000,000, you need a million-element count array even if you only have 10 input elements. That's wasteful. Counting sort only makes sense when the value range is reasonable.

Limitations

Counting sort is a non-comparison sort, so it doesn't compare elements against each other. This means it can't sort floating-point numbers directly (though you can adapt it). It also can't sort strings or custom objects without first mapping them to integer keys.

The biggest limitation is memory usage when the range k is large. Sorting 1 billion numbers that happen to be in the range 0-10 billion would require a 10 billion element array. In those cases, use radix sort instead — it combines counting sort with digit-by-digit processing to handle large ranges efficiently.