Counting Sort — Sorting

Overview

What this concept solves

Counting sort breaks the O(n log n) barrier by not comparing anything. Every comparison sort needs Ω(n log n) in the worst case — that's a proven lower bound. Counting sort sidesteps it entirely: instead of asking 'is a < b?', it asks 'how many of each value are there?' and uses the answer to place every element directly at its final position.

Three passes do the whole job. Pass 1 scans the input and tallies — count[v] ends up holding how many copies of value v exist. Pass 2 converts those tallies into a prefix sum: now count[v] holds the index where the last copy of v will end up. Pass 3 walks the input right-to-left and uses the prefix sums to drop each value at its final slot, decrementing the count after each placement. The result is sorted, in O(n + k) where k is the size of the value range.

The catch is that k. Counting sort uses a count array of size k+1, and you'll touch every slot of it during the prefix-sum pass. For small bounded ranges — bytes (k = 256), votes (k = number of candidates), exam scores (k = 100) — that's fine and the sort is blazingly fast. For 64-bit integers (k = 2⁶⁴), counting sort is laughably unsuitable. The right way to think about it: counting sort is for bounded small-key data, and it's the base case underneath radix sort.

Mechanics

How it works

Phase 1 — count

Allocate count[0 … k] and zero it.
For each v in the input: count[v]++.
After the pass, count[v] is the number of occurrences of value v.

Phase 2 — prefix-sum into end positions

For v from 1 to k: count[v] += count[v-1].
Now count[v] is the one-past-the-last slot index where value v will live in the output.
Equivalently: count[v] - 1 is where the last copy of v goes.

Phase 3 — place, right-to-left

Walk the input from index n-1 down to 0 (right-to-left — this is what makes the sort stable).
For each input value v: place it at output[count[v] - 1], then count[v]--.
After the loop, output is the sorted array.

Why right-to-left makes it stable

If two records have the same key v, the one earlier in the input gets placed first if we walk right-to-left — because we use count[v] - 1 (the rightmost free slot for v) and decrement. So the original left-to-right order of equal keys is preserved. A left-to-right pass would reverse them. Stability is what lets radix sort use counting sort as its inner pass.

When k matters more than n

If your input has n = 1000 elements but values span 0 to 10⁹, counting sort allocates a billion-slot array. That's not a sort, that's an OOM. The rule of thumb: counting sort is the right tool when k is O(n) or smaller. For larger k with smaller key-widths, switch to radix.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Counting Sort

About this simulation

Phase 1 counts how many times each value appears. Phase 2 turns the counts into running totals (= end positions). Phase 3 places each value at its slot, right-to-left. Press Play for the full sort, Step / Back to walk each phase, Shuffle for a new list.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Watch the three phases run end-to-end

Press Play. Watch the Phase stat change: Count (tallies climb), Prefix (counts turn into running totals), Place (each input value lands directly at its slot). Notice that the output array fills in out of input order during placement — counting sort doesn't move adjacent things together.

try 02

Step through the count phase

Use Step through Phase 1. Each tick of Operations is one increment. Watch the purple bar move across the count slots as each input value bumps its tally. After n increments, every value's count is locked.

try 03

See the prefix sum turn counts into positions

Step through Phase 2. Each count[v] += count[v-1] is one operation. After the prefix-sum, count[v] is no longer 'how many of v' — it's 'one past where v's last copy lands.' That's the precomputed lookup table the placement phase will use.

try 04

Shuffle and notice k matters, not n

Press Shuffle for a new random list of 9 values in [0, 9]. The total number of operations barely changes — it's always ≈ n + k. Try imagining the same algorithm on values in [0, 1 000 000]: the count array alone would dominate. That's why counting sort is for small-range integer data.

In practice

When to use it — and what you give up

When it's the right tool

Integer keys in a small known range — votes, ages, exam scores, byte values, palette indices.
As radix sort's inner pass — a stable O(n) per-digit sort is exactly what radix needs.
Histogram building — pass 1 alone is essentially Counter(items).
Stable bucketing — group by category while preserving input order within each category.

When to reach for something else

Floating-point or string keys — there's no natural finite count array. Use a comparison sort.
Wide integer ranges — k ≫ n means you're allocating more memory than you can fit. Switch to radix or comparison sort.
You can't afford O(n + k) extra memory — counting sort isn't in-place.

Pros

O(n + k) — linear when k is O(n) — the fastest sort known when the key range is bounded.
Stable — right-to-left placement preserves the input order of equal keys.
No comparisons — sidesteps the n log n lower bound for comparison sorts.
Foundation for radix sort — radix is just counting sort applied per digit.
Trivial to parallelise the count phase — each thread tallies its slice independently, then merge.

Cons

Not in-place — needs a count array of size k+1 and a separate output array of size n.
O(n + k) memory — unusable when k is huge.
Only works on integer-keyed data — or anything mappable to a small integer.
Doesn't adapt — sorted input takes the same work as random.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

counting-sort.ts

// Counting sort — stable, O(n + k), not in-place.
// Requires integer keys in [0, k].
function countingSort(a: number[], k: number): number[] {
  const n = a.length;
  const count = new Array(k + 1).fill(0);
  const out = new Array(n);

  // Phase 1: tally.
  for (let i = 0; i < n; i++) count[a[i]]++;

  // Phase 2: prefix-sum into end-position-plus-one.
  for (let v = 1; v <= k; v++) count[v] += count[v - 1];

  // Phase 3: place, right-to-left for stability.
  for (let i = n - 1; i >= 0; i--) {
    const v = a[i];
    out[--count[v]] = v;
  }
  return out;
}

// Example
countingSort([4, 2, 2, 8, 3, 3, 1], 8);
// → [1, 2, 2, 3, 3, 4, 8]
// Memory: O(n + k). Time: O(n + k).

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

Why does counting sort break the O(n log n) lower bound for comparison sorts?

question 02 / 03

When does counting sort become worse than mergesort?

question 03 / 03

Why does counting sort walk the input right-to-left in the placement phase?

0/3 answered