jsschools

Counting Sort

Non-comparison sort that counts element frequencies and reconstructs the sorted array using prefix sums; runs in linear time when the value range is small.

Spec ↗

Syntax

countingSort(arr, maxVal)

Parameters

NameTypeRequiredDescription
arr Array<number> Yes Array of non-negative integers to sort. Values must be in [0, maxVal].
maxVal number Yes The maximum value that can appear in arr. Determines the count array size.

Returns

Array<number> — A new sorted array; the original is not mutated.

Examples

function countingSort(arr, maxVal) {
  const count = new Array(maxVal + 1).fill(0);
  for (const x of arr) count[x]++;
  // prefix sum
  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;
}

console.log(countingSort([4, 2, 2, 8, 3, 3, 1], 8));
Output 
[ 1, 2, 2, 3, 3, 4, 8 ]

// Stable: equal elements preserve original order
function countingSort(arr, maxVal) {
  const count = new Array(maxVal + 1).fill(0);
  for (const x of arr) count[x]++;
  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;
}

// All same value
console.log(countingSort([3, 3, 3], 3));
Output 
[ 3, 3, 3 ]

Notes

| Case | Time | Space | |---------|------------|------------| | Best | O(n + k) | O(n + k) | | Average | O(n + k) | O(n + k) | | Worst | O(n + k) | O(n + k) | where k = maxVal. Counting sort is **stable** and extremely fast when k is O(n). It becomes impractical when k >> n (e.g. sorting 10 items with values up to 10^9 would need a 10^9-element count array). It only works on non-negative integers in its basic form. Counting sort is used as a subroutine in radix sort.

See also