Counting Sort

Sorting compact integer ranges by counting instead of comparing

Replace comparisons with frequencies

When values are integers from a manageable range, use one bucket per value. The first pass counts every occurrence. The second pass walks buckets from smallest to largest and writes each value back as many times as it was counted.

Watch counts enter and leave buckets

The main array stays unchanged during counting while the bucket track grows. During write-back, the green pointer advances through the array and each active bucket decreases to zero. No pair of input elements is ever compared.

Read the next value 3 and increment its bucket to 1.

1function countingSort(a: number[]): number[] {
const min = Math.min(...a), max = Math.max(...a);
const count = new Array(max - min + 1).fill(0);
for (let i = 0; i < a.length; i++) count[a[i] - min]++;
let w = 0;
for (let v = 0; v < count.length; v++) {
  while (count[v] > 0) {
    a[w++] = v + min;
    count[v]--;
  }
}
return a;
13}

n10

min1

max6

PhaseCount

1 / 27

Range size is the real constraint

For n values spanning k distinct integer positions, time is O(n + k) and bucket space is O(k). The method is excellent when k is close to n, but wasteful for a huge sparse range. This direct write-back version does not preserve record order; a prefix-count output array can make it stable.

Counting Sort is a domain-specific optimization. Validate the value range before allocating buckets, especially when input is user-controlled.

Return to the learning paths to compare comparison and non-comparison sorting.

Algorithm Visualizer

Counting Sort

Replace comparisons with frequencies

Watch counts enter and leave buckets

Range size is the real constraint