Vibe Engines
YouTube

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

Algorithm · Sorting

No Comparisons.

Watch the explainer

Don't memorize counting sort — watch it sort without comparing a single pair. When your values are small integers, you do not need to ask “which is bigger?” at all. Just tally how many times each value appears, then walk the tallies from low to high and emit each value that many times. The result falls out sorted — in linear O(n + k) time.

tally · buckets · emit in order · O(n + k)
COUNT ARRAY

One bucket per possible value, holding how many times it appears.

TALLY

Scan the input once, bumping count[value] for each element.

EMIT

Walk buckets low → high, output each value count[v] times.

NO COMPARE

Never asks which is bigger — so it beats the O(n log n) wall.

counting-sort.sim — sort [3,1,4,1,5,1,4], values 0…5
Ready

Top is the input; middle is a bucket for each value 0…5; bottom is the sorted output. Press Step to tally each input into its bucket, then emit the values in order — no comparisons anywhere.

Tally
Phase
0
Comparisons

Sorting by address, not by contest

Comparison sorts like quicksort and merge sort must ask “is a before b?” over and over, and information theory says that costs at least O(n log n). Counting sort sidesteps the whole question. If every value is a small integer, that integer is its address: value 4 goes in bucket 4, no contest needed. Count the buckets, then read them out in order. The only price is a count array the size of the value range.

01

Make the buckets

Allocate a count array with one slot per possible value, 0 through k, all zero.

02

Tally the input

One pass: for each element, increment count[value]. O(n), and not a single comparison.

03

Emit in order

Walk the counts from 0 to k, outputting each value count[v] times. O(k) plus the n outputs.

04

Make it stable

Use a prefix sum of the counts and place from the back of the input, so equal keys keep their order — the key to radix sort.

Time
O(n + k)
Space
O(n + k)
Comparisons
0
Stable
Yes*

The catch is k. When the value range is comparable to n, counting sort is a linear-time marvel; when k dwarfs n (say sorting a handful of 64-bit numbers), the count array is enormous and wasteful — reach for a comparison sort. Chaining stable counting sort one digit at a time gives radix sort, which sorts big numbers and strings in linear time relative to their length.

The picture: tally, accumulate, place

input3141514count[v]v = 00v = 13v = 20v = 31v = 42v = 51prefix: end position of each value033467output1113445
The page’s input [3, 1, 4, 1, 5, 1, 4] with values 0 to 5. The count row has one cell per possible value (the three 1s are highlighted). The prefix row says where each value’s block ends in the output. No two elements are ever compared.

Worked example, step by step

Sort [3, 1, 4, 1, 5, 1, 4], values 0 to 5. Pass 1 counts: count = [0, 3, 0, 1, 2, 1]. Pass 2 accumulates it into end positions: [0, 3, 3, 4, 6, 7]. Pass 3 walks the input from the back; for each value, decrement its end position and write the value there. That backward walk is what makes the sort stable.

Input indexValueWritten to output position
645
512
456
311
244
110
033

Read the rows top to bottom. The last 4 (index 6) lands at position 5 and the earlier 4 (index 2) at position 4, so equal keys keep their input order. The three 1s, taken back to front, land at positions 2, 1 and 0. Output: [1, 1, 1, 3, 4, 4, 5]. The total work was 7 reads to count, 6 steps over the count array, and 7 placements, with zero comparisons. If the elements were records (a name tagged with each number), the placement pass would carry the whole record, and records with equal keys would keep the order they came in. The simple “emit each value count times” version loses that, because it rewrites bare numbers.

Why stability matters: three passes of radix sort. Sort [170, 45, 75, 90, 802, 24, 2, 66] by running this stable counting sort on one decimal digit at a time, ones first. After the ones digit: [170, 90, 802, 2, 24, 45, 75, 66]. After the tens: [802, 2, 24, 45, 66, 170, 75, 90]. After the hundreds: [2, 24, 45, 66, 75, 90, 170, 802], sorted. Each pass uses only 10 counters, although the values reach 802. In the last pass six numbers share the hundreds digit 0, and only stability keeps them in the order the tens pass gave them. An unstable pass would throw that work away.

Complexity and trade-offs

CaseTimeSpaceWhy
Counting sortO(n + k)O(n + k)k is the value range. One pass to count, one over the buckets, one to place.
Quicksort / merge sortO(n log n)O(log n) / O(n)No assumptions about keys; limited by the comparison lower bound.
Radix sort (LSD)O(d · (n + b))O(n + b)d digits in base b, each a stable counting sort. Handles big integers.
Bucket sortO(n) expectedO(n)Needs input spread roughly uniformly over a range.
Counting sort on 32-bit keysO(n + 2³²)4,294,967,296 countersThe count array alone is billions of cells: absurd for 7 numbers.

Counting sort is only linear when k is O(n). For the 7-element example, k = 6 is fine; for the same 7 numbers drawn from 0 to 4 billion, you would allocate over four billion counters to sort seven values, and quicksort wins by a mile. Two refinements help: subtract the minimum so negative or offset ranges cost only (max − min + 1) cells, and chain digit passes (radix sort) when keys are wide.

Common mistakes

  • Count array one slot too short

    For values 0 to k you need k + 1 slots. Sizing it by max instead of max + 1 throws an out-of-range error the first time the maximum value appears, e.g. a 5 in [3, 1, 5].

  • Negative values

    count[-3] is not a counter; in Python it silently indexes from the end. Subtract the minimum first, so index = x − min, and add it back on output.

  • Placing from the front and losing stability

    Walking the input forwards with end positions reverses equal keys. The backward walk with a decrement, as in the trace, preserves order, and radix sort is only correct when every digit pass is stable.

  • Skipping the empty input

    max([]) raises an error. Return early for an empty list before sizing the count array.

  • Using it when k is huge

    Sorting timestamps or 64-bit ids by counting allocates a range-sized array. The symptom is an out-of-memory error on a ten-element input. Check k against n first, or reach for radix sort.

Where this shows up

  • The inner loop of radix sort

    Least-significant-digit radix sort runs a stable counting sort once per digit. With 8-bit digits, each pass uses only 256 counters, which is why it can sort 32-bit keys in four passes.

  • Suffix array construction

    Prefix-doubling suffix array algorithms sort pairs of ranks with radix passes built on counting sort, giving O(n log n) rather than O(n log² n).

  • Image histograms

    An 8-bit grayscale image has 256 possible pixel values, so counting them is a 256-bucket tally. Histogram equalisation uses the cumulative count (the prefix row) to remap brightness.

  • Sort Colors and small-range data

    Grades, ages, ratings and letter frequencies all have tiny ranges. The counting version of LeetCode 75 “Sort Colors” is a two-pass counting sort with three buckets.

SOLVE IT YOURSELF

Solve it: counting sort

This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.

YOUR TASK

Implement counting_sort(nums) for non-negative integers — no comparisons and no built-in sort. Tally how many times each value appears in a count array, then emit each value that many times in order. O(n + k), where k is the largest value.

HINTS — 4 IDEAS
  1. Find the maximum value; make a count array of that many + 1 slots, all zero.
  2. One pass over the input: count[x] += 1 for each value x.
  3. Walk the count array from 0 upward; append value v exactly count[v] times.
  4. Handle the empty input (return an empty list) so max is never called on nothing.
CPython · WebAssembly

Check yourself

1 · How does counting sort place a value?

The value is its own address — it goes straight into count[value], no comparison needed.

2 · What is the time complexity of counting sort?

One pass to tally n elements plus one pass over k+1 buckets to emit — linear in n plus k.

3 · When is counting sort a poor choice?

A huge k means a huge, mostly-empty count array — wasteful. Use a comparison sort when k dwarfs n.

Questions

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

That bound only applies to sorts that learn order by comparing elements. Counting sort never compares — it uses each value as an index — so the bound simply does not apply. The cost is that it only works on integer-like keys in a bounded range.

What is the difference from bucket sort?

Bucket sort scatters values into a few ranges (buckets) and sorts each bucket, good for uniformly distributed reals. Counting sort has one bucket per exact value and never sorts within a bucket. They share the bucketing idea but suit different data.

Why does radix sort need counting sort to be stable?

Radix sort sorts by the least significant digit first, then the next, and so on. Each pass must preserve the order established by the previous digits, which requires a stable sub-sort — and stable counting sort provides exactly that.

Count, then pour it out in order.

No swaps, no comparisons — just tallies and a walk from low to high. Linear sorting for bounded keys.

▶  Watch it explained

Counting Sort: Time and Space Complexity, From First Principles

Finished this one? 0 / 99 Algorithms done
NextScatter, Sort, Gather: Bucket Sort Next on the “Beating n log n” ladder · rung 2 of 4

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Algorithms