Skip to content

level 3 · Sorting

Counting Sort

Sorts without comparing anything — and that's how it beats n log n.

9 min 75 XP

what is it

Start here

There's a famous theorem that says no sorting algorithm can beat n log n. Counting sort beats it. Both statements are true, and the resolution is the most interesting thing in this lesson.

The theorem's exact words are: no **comparison** sort can beat n log n. Every sort you've met so far works by asking 'is this bigger than that?' — and it turns out you can't get to the answer in fewer than n log n such questions. It's a hard mathematical floor.

Counting sort simply doesn't ask that question. Not once. It tallies: how many 0s, how many 1s, how many 2s. Then it reads the tallies back out in order. Zero comparisons, so the theorem never applies to it. It sidesteps the wall instead of climbing it.

Nothing is free, though, and the price here is very specific. You must know the range of values in advance, and the memory you need is that **range**, not the size of the input. Sort five numbers that happen to be a billion apart, and you need a billion counters to do it. Counting sort is superb on 'ages 0–120' and useless on arbitrary integers.

real-life analogy

Picture it

Sorting a class by age with a show of hands

Don't compare students to each other. Just call out: 'hands up if you're 14.' Count. 'Hands up if you're 15.' Count. Then read the ages back in order and you have them sorted — without any two students ever being compared. It only works because you knew the ages ran from about 11 to 18.

interactive visualization

Watch it run

Phase 1 tallies. Phase 2 reads the tallies back out. Zero comparisons.

  1. 4
  2. 2
  3. 7
  4. 1
  5. 4
  6. 2
  7. 6
  8. 4

Counting sort never compares two values against each other. Not once. It just counts how many of each there are — and that's how it beats the n log n limit that binds every comparison sort.

step 01/18

  • comparing
  • moving
  • in final place
1// No comparisons at all. It counts instead.
2function countingSort(a, maxValue) {
3 const count = new Array(maxValue + 1).fill(0);
4
5 // 1. How many of each value?
6 for (const v of a) count[v]++;
7
8 // 2. Read them back out, smallest first.
9 const out = [];
10 for (let v = 0; v <= maxValue; v++) {
11 for (let k = 0; k < count[v]; k++) out.push(v);
12 }
13
14 return out;
15}

variables right now

n
8
maxValue
7
comparisons 0moves 0

the dry run · every step, in words

18 steps

complexity

What it costs

best case
O(n + k)
average
O(n + k)
worst case
O(n + k)
extra memory
O(k)

Linear in n + k, where k is the RANGE of values (not the count). That beats n log n — legitimately, because the n log n floor only binds comparison sorts. But the memory is k: a small range is wonderful, a huge range is catastrophic.

  • O(1)
  • O(log n)
  • O(n) · this one
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Using it when the range of values is huge.

    The memory is the range, not the input size. Eight values spread across a billion needs a billion counters. Check the range before you reach for this.

  • Believing it disproves the n log n lower bound.

    It doesn't. That bound only applies to *comparison* sorts, and counting sort makes zero comparisons. It's not breaking the rule — the rule was never about it.

  • Forgetting to handle negative numbers.

    count[v] with a negative v is an out-of-bounds crash. Offset every value by the minimum first, or the very first negative number kills it.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+75 XP

01How does counting sort beat the n log n lower bound?

02What is 'k' in O(n + k)?

03When is counting sort a terrible choice?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.