Counting Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Counting Sort

An efficient, non-comparison-based sorting algorithm that runs in linear time. It works by counting the occurrences of each key within a specific range.

How it works

Counting Sort bypasses the O(n log n) comparison-based sorting limit by exploiting key distributions. It works under the assumption that the input values lie within a known, relatively small range from a minimum to a maximum value.

1. Find the range of elements by identifying the minimum and maximum values in the input array.
2. Create a helper array count of size equal to this range, initialized to zero.
3. Scan the input array and count the occurrences of each number, storing the counts in the count array.
4. Calculate the prefix sums of the counts to find the exact starting position of each number in the output.
5. Build the sorted output array by scanning the input array in reverse, placing elements in their correct indices, and decrementing their counts to preserve stability.
6. Copy the output array back to the original array.

Complexity

Interactive visualization

Pseudocode

procedure countingSort(A):
  n ← length(A)
  min, max ← findMinMax(A)
  range ← max - min + 1
  count ← array of size range initialized to 0
  output ← array of size n
  
  for i from 0 to n - 1:
    count[A[i] - min] ← count[A[i] - min] + 1
    
  for i from 1 to range - 1:
    count[i] ← count[i] + count[i - 1]
    
  for i from n - 1 down to 0:
    val ← A[i]
    pos ← count[val - min] - 1
    output[pos] ← val
    count[val - min] ← count[val - min] - 1
    
  for i from 0 to n - 1:
    A[i] ← output[i]

JavaScript implementation

function countingSort(arr) {
  const n = arr.length;
  if (n <= 1) return arr;

  let min = arr[0];
  let max = arr[0];
  for (let i = 1; i < n; i++) {
    if (arr[i] < min) min = arr[i];
    if (arr[i] > max) max = arr[i];
  }

  const range = max - min + 1;
  const count = new Array(range).fill(0);
  const output = new Array(n);

  for (let i = 0; i < n; i++) {
    count[arr[i] - min]++;
  }

  for (let i = 1; i < range; i++) {
    count[i] += count[i - 1];
  }

  for (let i = n - 1; i >= 0; i--) {
    const val = arr[i];
    const pos = count[val - min] - 1;
    output[pos] = val;
    count[val - min]--;
  }

  for (let i = 0; i < n; i++) {
    arr[i] = output[i];
  }
  return arr;
}

Pros and cons

When to use it

• Tight Key Range: when sorting integer datasets where range $k$ is roughly proportional to $n$ (such as grades, ages, or status flags).
• As a subroutine: commonly used as the stable sorting engine inside Radix Sort.