Counting Sort Visualizer: Step-by-Step Animation & Complexity

Counting Sort

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

Input Data

Visualization

Visual representation of the data structure

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;
}

Variable State

{
  "arr": "[4, 2, 2, 8, 3, 3, 1]",
  "max": 8
}

Counting Sort: How It Works

Last updated October 28, 2026

Overview

Counting Sort does not compare elements at all. It counts how many times each value occurs, turns those counts into positions, and then places each element directly into its slot in the output array. That lets it beat the O(n log n) limit that applies to comparison sorts.

The version here supports negative numbers by offsetting every value by the minimum (arr[i] - min). After counting, a running total (prefix sum) turns count[v] into 'how many elements are less than or equal to v', which is exactly the 1-based position of the last v.

Walking the input from right to left while placing elements keeps equal values in their original order, which makes the algorithm stable. That stability is what Radix Sort relies on. With the default input 4, 2, 2, 8, 3, 3, 1 the range is 1..8, so the count array has eight slots.

Step by step

Find min and max and create a count array of size max - min + 1.
For every element, increment count[value - min].
Convert count into prefix sums so each entry holds an end position.
Walk the input backwards; put each value at output[count[value - min] - 1] and decrement that count.
Copy output back into the original array.

Complexity

Case	Cost	Why
Best case	O(n + k)	k is the value range `max - min + 1`; every pass is linear.
Average case	O(n + k)	No dependence on input order.
Worst case	O(n + k)	Becomes impractical when k is much larger than n.
Extra space	O(n + k)	The count array plus the output array.

When to use it

Integers (or keys that map to integers) with a small range, such as ages, grades or byte values.
As the stable per-digit pass inside Radix Sort.
Histogram-style problems where you need the counts anyway.

Common mistakes

Memory explodes when the range is large: sorting two values, 0 and 1,000,000,000, needs a billion counters.
Iterating forwards in the placement loop still sorts correctly but loses stability.
It does not work directly on floating-point or arbitrary objects without a key-to-integer mapping.

Worked Example: Counting Sort Dry Run

Generated from the same trace that drives the visualizer above, using the default input.

A dry run is the best way to check your understanding of Counting Sort: follow each row, predict the next one, and compare. The run below takes 69 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.

Input: 4, 2, 2, 8, 3, 3, 1
Result: return value = [1, 2, 2, 3, 3, 4, 8]

Step	Line	Array	What happens
1	2	[4, 2, 2, 8, 3, 3, 1]	max = 8
56	18	[1, 2, 2, 8, 3, 3, 1]	i = 0
62	18	[1, 2, 2, 3, 3, 3, 1]	i = 3
66	18	[1, 2, 2, 3, 3, 4, 1]	i = 5
68	18	[1, 2, 2, 3, 3, 4, 8]	i = 6
69	20	[1, 2, 2, 3, 3, 4, 8]	return value = [1, 2, 2, 3, 3, 4, 8]

Frequently Asked Questions

About Counting Sort

What is Counting Sort?

Counting Sort is a non-comparison based integer sorting algorithm. It operates by counting the number of occurrences of each distinct element in the input array and uses arithmetic on these counts to determine the final position of each element.

What is the time complexity of Counting Sort?

The time complexity is O(n + k), where n is the number of elements in the input array and k is the range of the integer values (max - min + 1). It is extremely fast if the range k is not significantly larger than n.

What are the limitations of Counting Sort?

Its main limitation is that it's only efficient for integers with a relatively small range. If the range (k) is very large (e.g., sorting 32-bit integers), the algorithm becomes impractical due to the large size of the counting array needed. It also doesn't work for non-integer types like floats or strings.

Is Counting Sort stable?

Yes, when implemented correctly, Counting Sort is a stable algorithm. This property is crucial for its use as a subroutine in Radix Sort. Stability is achieved by processing the input array from end to beginning when placing elements into the output array.

How does Counting Sort use its 'count' array?

First, the count array stores the frequency of each element. Then, it's modified so that each index stores the cumulative count (the sum of all previous counts). This cumulative count directly tells you the final position of each element in the sorted output array.

Why is Counting Sort not a comparison-based sort?

It does not compare elements against each other. Instead, it uses the element values themselves as indices into an array to count them, which is why it can break the Ω(n log n) lower bound for comparison sorts.

What is the space complexity of Counting Sort?

The space complexity is O(k) to store the count array. This can be a major drawback if k is large.

How would you handle negative numbers in Counting Sort?

To handle negative numbers, you can offset the values by the minimum value in the array. When indexing the `count` array, you would use `arr[i] - min`, and when placing elements in the output, you would add `min` back.

Is Counting Sort an in-place algorithm?

No, it is not. It requires an auxiliary `count` array of size k and an `output` array of size n, so it is not an in-place sorting algorithm.

When is Counting Sort better than Quick Sort?

Counting Sort is better than Quick Sort when the data is a set of integers within a small, known range. In this scenario, its O(n + k) performance will be significantly faster than Quick Sort's O(n log n).

Where can I learn more?

You can find a more detailed explanation on GeeksforGeeks.