Counting Sort

Sorting

avgO(n + k)worstO(n + k)spaceO(n + k)

main

out

count

Values range from 35 to 95

1 / 56

Code

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

procedure countingSort(A)  min ← minimum(A); max ← maximum(A)  count ← array of (max − min + 1) zeros  for each x in A do count[x − min] ← count[x − min] + 1  for v ← 1 to max − min do count[v] ← count[v] + count[v − 1]  out ← new array of size n  for i ← n − 1 down to 0 do    ▷ backwards keeps it stable    count[A[i] − min] ← count[A[i] − min] − 1; out[count[A[i] − min]] ← A[i]  end for  copy out back into A  return Aend procedure

Variables

min=35max=95

Counters

reads: 0
writes: 0

Size24

Distribution

Custom values2 to 150 whole numbers, each 1 to 999

seed 9

How it works

Never compares elements: it tallies how often each value occurs, turns the tally into prefix sums (each value's end position), then places every element straight into the output. It runs in linear time when the value range k is small.

Complexity

Best: O(n + k)
Average: O(n + k)
Worst: O(n + k)
Space: O(n + k)
Stable: Yes
In place: No

Counting Sort

How it works

Complexity

Search algorithms