Counting Sort

non-comparisonstableinteger-sort

Press play to start

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

Step 1/0

Custom array:

Complexity

Best:O(n+k)
Average:O(n+k)
Worst:O(n+k)
Space:O(k)

Description

Counts the occurrences of each value, then reconstructs the sorted array by iterating over the count array.

When to use

O(n+k) time for non-negative integers with small range k. Ideal for sorting integers, characters, or categorical data.