AlgoViz: Interactive Algorithm Visualization Tool

Counting Sort

Category: Sorting | Time: O(n + k) | Space: O(k)

Input Data

Visualization

Visual representation of the data structure

Enter an algorithm and input to start visualization.

About Counting Sort

An integer sorting algorithm that operates by counting the number of objects that have each distinct key value. It is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items.

Code Editor

The code is for reference. Editing it won't affect the visualization.

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

What is Counting Sort?

What is the time complexity of Counting Sort?

What are the limitations of Counting Sort?

Is Counting Sort stable?

How does Counting Sort use its 'count' array?

Why is Counting Sort not a comparison-based sort?

What is the space complexity of Counting Sort?

How would you handle negative numbers in Counting Sort?

Is Counting Sort an in-place algorithm?

When is Counting Sort better than Quick Sort?

Where can I learn more?