Counting Sort

Counting sort belongs to a family of non-comparison sorts. Instead of asking “is A less than B?”, it counts how many elements equal each possible value, then uses those counts to place each element directly into its correct output position. Because it never compares two elements, it is not subject to the Ω(n log n) lower bound.

The Three-Step Algorithm

1. Count — create an array count of length k + 1 (where k is the maximum value). Increment count[v] for each element with value v.
2. Prefix sum — replace each count[i] with the sum of all counts up to and including i. Now count[v] holds the number of elements with value ≤ v, which is exactly the index (1-based) of the last occurrence of v in the output.
3. Place — iterate the input from right to left. For each element v, place it at output position count[v] - 1, then decrement count[v]. Right-to-left traversal is what makes the sort stable.

JavaScript Implementation

function countingSort(arr, maxVal) {
  const n = arr.length;
  const count = new Array(maxVal + 1).fill(0);
  const output = new Array(n);

  // Step 1: count occurrences
  for (let i = 0; i < n; i++) {
    count[arr[i]]++;
  }

  // Step 2: prefix sums — count[i] now holds number of elements <= i
  for (let i = 1; i <= maxVal; i++) {
    count[i] += count[i - 1];
  }

  // Step 3: place elements right-to-left to preserve stability
  for (let i = n - 1; i >= 0; i--) {
    output[count[arr[i]] - 1] = arr[i];
    count[arr[i]]--;
  }

  return output;
}

console.log(countingSort([4, 2, 2, 8, 3, 3, 1], 8));
// => [1, 2, 2, 3, 3, 4, 8]

Stability Explained

The right-to-left traversal in Step 3 ensures that among elements with the same value, the one that appeared last in the input is placed last in the output — preserving their original relative order. This stability property is what makes counting sort suitable as the inner sort in radix sort.

Complexity

Here k is the range of input values (maxVal − minVal + 1).

When Counting Sort Wins

Counting sort is ideal when k is small relative to n — for example, sorting exam scores (0–100) for a class of 1,000 students, or sorting single bytes in a radix sort pass. It is the wrong choice when k is large (sorting 32-bit integers with k ≈ 4 billion would need 4 GB of count space) or when elements are not non-negative integers.

Handling Negative Numbers

Subtract the minimum value from every element before sorting and add it back afterward. This shifts the range to start at 0 without changing the relative order.

Up Next

Radix sort extends the counting-sort idea to multi-digit numbers, sorting digit by digit from least significant to most significant.