FlowLab Logo

Counting Sort Visualizer

SlowFast
Current Phase: Counting Elements

Input Array

4
[0]
2
[1]
2
[2]
8
[3]
3
[4]
3
[5]
1
[6]
Operation Logs
No operations yet
Algorithm Info
Time Complexity: O(n + k) where k is the range of input
Space Complexity: O(k) for the counting array
Stable: Yes - maintains relative order of equal elements
Non-comparison: Does not compare elements, counts occurrences instead
Best for: Small range of integer values, when k is not significantly larger than n
Limitation: Only works with non-negative integers or needs modification for negative numbers
Implementation
function countingSort(arr) {
  const n = arr.length;
  const max = Math.max(...arr);
  const min = Math.min(...arr);
  const range = max - min + 1;

  const count = new Array(range).fill(0);

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

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

  const output = new Array(n);
  for (let i = n - 1; i >= 0; i--) {
    const element = arr[i];
    const index = element - min;
    output[count[index] - 1] = element;
    count[index]--;
  }

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

  return arr;
}