Counting Sort Visualizer

There is a theorem stating that no comparison-based sort can beat O(n log n). Counting sort runs in O(n + k). Both are correct, because counting sort never compares two elements to each other — it uses their values directly as array indices, which is a different kind of operation entirely and sits outside the theorem's reach.

That trick has a price. Counting sort needs to know the range of possible values in advance, and it allocates memory proportional to that range. Sorting a million integers between 0 and 100 is spectacularly fast. Sorting three integers that happen to include 2,000,000,000 is a catastrophe.

What is counting sort?

Counting sort works in three passes over the data. First, tally how many times each distinct value appears. Second, turn those tallies into running totals, so each entry says 'this many elements are less than or equal to me'. Third, walk the input and place each element directly at the position its running total specifies.

No element is ever compared with another element. The only comparisons in the entire algorithm are loop bounds. Values are used as addresses — the count of value v lives at index v — and that indirection is what breaks the O(n log n) barrier.

The consequence is a hard constraint: values must be non-negative integers, or something that maps cleanly onto them. You cannot counting-sort arbitrary floats, strings or objects without first defining such a mapping, and if that mapping has a large range the algorithm becomes useless.

Why it works

After the prefix-sum pass, count[v] holds the number of elements less than or equal to v. That number is exactly the position immediately after where the last v belongs in the sorted output — so decrementing it and writing there places a v correctly, and leaves the counter pointing at the slot for the *previous* v.

This is worth restating because it is the crux. If there are three 5s and seven elements are ≤ 5, then the 5s occupy output positions 5, 6 and 7 (one-indexed). The running total 7 points at the last of them; decrement to 6 for the next 5, then 5 for the one after. Each value's block of slots is filled from the back.

Because every element's destination is computed rather than searched for, there is no ordering work at all in the placement pass. The sort is complete the moment the last element is written.

Step-by-step walkthrough

Take [4, 2, 2, 8, 3, 3, 1], with values in the range 0–8.

1. Tally. Walk the input incrementing counters: count = [0, 1, 2, 2, 1, 0, 0, 0, 1] — one 1, two 2s, two 3s, one 4, one 8.
2. Prefix sum. Accumulate left to right: count = [0, 1, 3, 5, 6, 6, 6, 6, 7]. Now count[3] = 5 means five elements are ≤ 3.
3. Place, right to left. The last input element is 1. count[1] is 1, so decrement to 0 and write 1 at index 0.
4. Next is 3. count[3] is 5, so decrement to 4 and write 3 at index 4. Then the other 3 goes to index 3.
5. Continue with 8 → index 6, 2 → index 2, 2 → index 1, 4 → index 5. Result: [1, 2, 2, 3, 3, 4, 8].

The k problem, stated plainly

The complexity is O(n + k), where n is the number of elements and k is the size of the value range. Everything about whether counting sort is a good idea comes down to the relationship between those two numbers.

When k is comparable to or smaller than n, counting sort is exceptional. Sorting a million exam scores in the range 0–100 means k = 101, so the cost is essentially O(n) — a single-digit multiple of just reading the data, and dramatically faster than any comparison sort.

When k is much larger than n, it is a disaster. Sorting ten 32-bit integers requires a count array of four billion entries, which is 16 GB of memory to sort ten numbers. The algorithm does not degrade gracefully; it fails outright.

The practical rule: use counting sort when the value range is known, bounded and roughly proportional to the input size. When the range is large but the values have structure, use radix sort, which applies counting sort digit by digit and keeps k fixed at 10 (or 256) regardless of how large the numbers get. That is the standard escape from the k problem, and it is why counting sort's stability matters so much.

How the animation above works

The visualiser shows the phases the algorithm actually performs: a read-only tally pass over every element, the prefix-sum accumulation, and then the placement pass that writes the finished array back. Because the counting happens in a separate table rather than in the bars, you will see a long run of reads producing no visible movement, followed by every position being written exactly once.

That shape is the whole point. Compare it with bubble sort at the same size in the comparison lab: bubble sort's bars churn continuously for thousands of operations, while counting sort reads everything once, thinks, and then writes the answer. The comparison counter for counting sort stays flat, because it never compares two elements at all.

Time complexity

O(n + k) in the best, average and worst case. There are three linear passes over the input plus one pass over the count array of size k. No input arrangement changes any of this — sorted, reversed and random data cost precisely the same.

The absence of a worst case is unusual and genuinely useful. Unlike quick sort, there is no adversarial input; unlike insertion sort, there is no lucky one. The cost is a function of n and k alone.

The lower bound of Ω(n log n) for sorting does not apply here because that bound is proved over the decision tree of comparison-based algorithms: with only comparisons available, distinguishing n! possible orderings requires log₂(n!) ≈ n log n decisions. Counting sort makes no such decisions. Using a value as an index extracts far more information in one operation than a yes/no comparison can, so the bound simply does not constrain it.

Space and stability

O(n + k) auxiliary space: an output array of size n plus a count array of size k. This is counting sort's other cost, and it is not optional — the output must be built separately, because writing into the input would destroy elements not yet placed.

Stable, provided the placement pass runs right to left. This is not a nicety. Radix sort works by applying counting sort once per digit, and it depends entirely on each pass preserving the order established by the previous ones. A counting sort that walks forwards still produces sorted output on its own, but silently breaks any radix sort built on top of it — a bug that only shows up in the composed algorithm.

Handling negative numbers costs nothing structurally: find the minimum value and offset every index by it, so the count array covers min..max rather than 0..max. The visualiser does exactly this.

Complexity at a glance

The numbers below are what the counters in the visualiser converge on. Raise the array size and watch the comparison count grow at the rate this table predicts.

Pseudo code

Language-agnostic, and close enough to the implementations below that you can read them side by side.

Counting Sort in five languages

Working reference implementations — copy or download any of them. They are written to be read, so the comments explain the decisions rather than restating the code.

/**
 * Counting sort. O(n + k) where k is the size of the value range.
 * Handles negatives by offsetting every index by the minimum value.
 */
function countingSort(arr) {
  if (arr.length === 0) return arr;

  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const count = new Array(max - min + 1).fill(0);

  // Pass 1: tally.
  for (const value of arr) count[value - min]++;

  // Pass 2: running totals. count[i] is now "how many values <= i".
  for (let i = 1; i < count.length; i++) count[i] += count[i - 1];

  // Pass 3: place. Walking backwards is what makes this stable.
  const output = new Array(arr.length);
  for (let i = arr.length - 1; i >= 0; i--) {
    const value = arr[i];
    output[--count[value - min]] = value;
  }

  for (let i = 0; i < arr.length; i++) arr[i] = output[i];
  return arr;
}

console.log(countingSort([4, 2, 2, 8, 3, 3, 1])); // [1, 2, 2, 3, 3, 4, 8]

Advantages and disadvantages

Real-world applications

• The per-digit engine inside radix sort, which is by far its most important use — this is why its stability matters.
• Sorting records by a bounded category: star ratings, priority levels, HTTP status codes, exam grades, age brackets.
• Histogram and frequency computation, where the count array is the actual output and the sort is incidental.
• Suffix array construction and other string algorithms, where characters map naturally onto a small alphabet.
• Image processing over 8-bit channels, where k is fixed at 256 regardless of image size — median filters and histogram equalisation both rely on this.
• Sorting large volumes of small integers in data pipelines, such as bucketing events by day-of-year or hour.

Interview questions

The questions that actually get asked about Counting Sort, with the answers an interviewer is listening for.

1. Q1. How does counting sort beat the O(n log n) lower bound?

   That bound applies only to comparison-based sorts. Its proof counts decision-tree leaves: with yes/no comparisons you need log₂(n!) ≈ n log n decisions to distinguish n! orderings. Counting sort never compares two elements — it uses each value directly as an array index, which extracts far more information per operation than a binary comparison. The theorem does not apply to it.

2. Q2. When would counting sort be a bad choice?

   Whenever k is much larger than n. Sorting ten 32-bit integers would require a count array of four billion entries — about 16 GB — to sort ten values. It is also unusable on floats, strings or anything sorted by a comparator. The rule of thumb is to use it only when the value range is bounded and roughly proportional to the input size.

3. Q3. Why does the placement loop iterate backwards?

   For stability. Walking right to left and decrementing the counter before writing means the last occurrence of a value in the input claims the last of that value's output slots, preserving the original relative order of equal elements. Walking forwards still sorts correctly but reverses equal elements — which silently breaks radix sort, since radix depends on each digit pass preserving the previous ones.

4. Q4. How would you counting-sort an array containing negative numbers?

   Find the minimum and offset every index by it, so the count array spans min..max instead of 0..max, with size max − min + 1. Value v maps to index v − min. Nothing else changes, and k becomes the width of the range rather than the maximum value — which also helps when all values are large but clustered.

5. Q5. What is the relationship between counting sort and radix sort?

   Radix sort is counting sort applied repeatedly, once per digit, from least significant to most. Each pass uses k = 10 for base 10 (or 256 for byte-wise), so the memory problem disappears no matter how large the numbers are. It only works because counting sort is stable: each pass must preserve the ordering that earlier passes established.

Common mistakes

• Iterating forwards in the placement pass, which produces sorted output but destroys stability — and therefore breaks any radix sort built on top of it.
• Sizing the count array as max instead of max - min + 1, which wastes memory and breaks entirely on negative input.
• Forgetting the - min offset when indexing, producing negative indices on negative values.
• Incrementing rather than decrementing the counter during placement, which writes every equal element to the same slot.
• Writing the output directly into the input array, which overwrites elements that have not yet been placed.
• Applying it to floating-point values by truncating them, which silently loses precision and produces wrong results.
• Computing min and max in a way that fails on an empty array, which is the one input everybody forgets to test.

Optimisation tips

• Skip the prefix-sum and placement passes entirely when you only need sorted output of plain integers — just walk the count array and emit each value the recorded number of times. This is simpler and uses less memory, but it is not stable and cannot carry associated records.
• Compute min and max in a single pass rather than two, especially on large arrays where the memory bandwidth matters more than the arithmetic.
• When the range is large but sparse, use a hash map for counts, or switch to radix sort — the latter is almost always the better answer.
• For byte-oriented data, fix k at 256 and use a stack-allocated count array, which avoids heap allocation entirely.
• Reuse the count array across calls when sorting many batches with the same range; zeroing 256 entries is far cheaper than reallocating.
• Parallelise the tally pass with per-thread count arrays that are summed at the end — it is a textbook reduction and scales nearly linearly.

Summary

Counting sort tallies how many times each value occurs, converts those tallies into running totals that name each value's position in the output, and then places every element directly at its computed destination. It never compares two elements, which is how it achieves O(n + k) and sidesteps the Ω(n log n) lower bound for comparison sorts.

The catch is k. When the value range is bounded and comparable to n — exam scores, star ratings, byte values — counting sort is the fastest option available and has no worst case at all. When the range is large it fails outright rather than degrading. For large-ranged integers the answer is radix sort, which runs counting sort once per digit and depends on the stability that walking the placement pass backwards provides.

Frequently asked questions

Related algorithms

• Radix Sort

  Sort by one digit at a time, least significant first, using a stable counting pass.

  O(d·(n + k))Advanced

• Merge Sort

  Split the array down to single elements, then merge sorted halves back together.

  O(n log n)Intermediate

• Bubble Sort

  Repeatedly swap adjacent pairs until the largest values have bubbled to the end.

  O(n²)Beginner