How does counting sort produce sorted output without ever comparing two elements?

juniormust knowfreq 65%

answer

The key itself is the address
Two sweeps before anything is written
Tallies become running totals
count[v] ends up meaning keys <= v
A running total is an end index

basics

~20 s

Counting sort tallies how often each key value occurs, then turns the tallies into running totals that say where each key's block ends. A final pass copies each record into its slot — position comes from arithmetic, never comparisons.

solid answer

~50 s

It uses the key itself as an index. Take an image pass that sorts pixel records by an 8-bit luminance value: allocate count with one slot per possible key, sweep the input once incrementing count[luminance], then sweep count turning the tallies into running totals, so count[v] becomes the number of keys <= v. That running total is an address: it says where value v's block ends in the output. A third pass walks the input and drops each record at its computed slot, decrementing the counter as it goes. Nothing is ever compared to anything — the ordering comes from the fact that array indices are already ordered. Cost is O(n + k) time and O(n + k) space for n records over a key range of size k, and the output lands in a separate buffer, so it is not in-place.

It uses the key itself as an index. Take an image pass that sorts pixel records by an 8-bit luminance value: allocate `count` with one slot per possible key, sweep the input once incrementing `count[luminance]`, then sweep `count` turning the tallies into running totals, so `count[v]` becomes the number of keys `<= v`. That running total is an address: it says where value `v`'s block ends in the output. A third pass walks the input and drops each record at its computed slot, decrementing the counter as it goes. Nothing is ever compared to anything — the ordering comes from the fact that array indices are already ordered. Cost is O(n + k) time and O(n + k) space for n records over a key range of size k, and the output lands in a separate buffer, so it is not in-place.

code

pseudocode · 10 lines

pseudocode

// keys are byte-valued: 0..k-1, with k = 256
for v in 0..k-1:
    count[v] = 0
for i in 0..length(a)-1:
    count[key(a[i])] = count[key(a[i])] + 1
// turn tallies into running totals
for v in 1..k-1:
    count[v] = count[v] + count[v-1]
// count[v] is now how many keys are <= v
...

go deeper

for a junior

Be ready to name the three passes in order — histogram, prefix sums, placement — and to say what the counters hold after each one. Knowing that the key is used as an index is the whole idea.

for a middle

Explain why the prefix-sum pass exists at all: it converts frequencies into output addresses. Be able to derive the index mapping for a key range that does not start at zero, and to state the space cost honestly.

for a senior

Show that you treat O(n + k) as two terms, and that you check the key range before reaching for this. Expect to justify the extra output buffer and the counter memory against whatever the general-purpose sort already costs.

for a principal

Own the framing that counting sort trades memory and an assumption about the data for time. Be ready to say which assumption you are prepared to depend on in a shared codebase and who owns keeping it true.

The idea

Every comparison-based sort discovers order by asking "is this key smaller than that one?". Counting sort never asks. It assumes the keys are small non-negative integers (or can be mapped to them), and exploits the fact that the slots of an array are already in order: if you can turn a key into an index, you can turn a bag of keys into a sorted sequence by arithmetic alone.

A concrete setting: an image-processing stage holds one record per detected pixel region, each carrying an 8-bit average-luminance key in 0..255 plus a payload (region id, bounding box). Here n can be tens of millions while k, the size of the key range, is fixed at 256.

The three passes

Pass 1 — histogram. Zero a count array of size k, then sweep the input once: count[key(a[i])] += 1. Now count[v] is how many records carry luminance v. This pass is O(n); the zeroing is O(k).

Pass 2 — prefix sums. Sweep count left to right accumulating: count[v] += count[v-1]. The array no longer holds frequencies; count[v] is now the number of keys less than or equal to v. Read as an address, that is the exclusive end of value v's block in the sorted output: all records with luminance v occupy the slots [count[v-1], count[v]). This is the step candidates skip, and skipping it is why they cannot say where a record goes. It costs O(k).

Pass 3 — placement. Walk the input, and for each record with key v decrement count[v] and write the record at the resulting index. Each block fills from its last slot toward its first, so after n writes every record sits in its own slot with its payload intact. This pass is O(n).

Total: O(n + k) time, O(n + k) space — n for the output buffer, k for the counters.

Why not just re-emit the counts?

There is a shorter variant: after the histogram, walk v from 0 to k-1 and write value v out count[v] times, overwriting the input. It is in-place and needs no output buffer, and it is a perfectly good way to sort a bare array of small integers. It is also useless the moment a key has a payload attached — the region id, the bounding box, the timestamp — because re-emitting a key value cannot reconstruct the record it came from. Real inputs are records, which is why the prefix-sum-plus-placement form is the one worth knowing.

Keys that do not start at zero

The algorithm indexes by key, so the key range must be mapped onto 0..k-1. For sensor readings in -40..60, the map is index = key - min, with k = max - min + 1 = 101 counters. Forgetting the offset indexes negatively; sizing the array max - min instead of max - min + 1 loses or corrupts the largest key. Both are boundary bugs, not design flaws: deriving min and max in one extra O(n) pass is cheap and makes the mapping explicit.

What the cost model actually says

The time is O(n + k), not O(n). Two terms, and each can dominate. For the 256-value luminance case k is a small constant and the whole thing is linear in the number of records, which is exactly where counting sort demolishes a comparison sort. The claim collapses when the key range is wide: the counters have to be allocated, zeroed and swept whether or not the input contains a single record with those keys. Being an upper bound on both terms, O(n + k) also says nothing about constants — but here the constants are tiny, since every pass is a straight sweep with no branching on data.

One pleasant consequence of never comparing: the running time does not depend on input order at all. Already sorted, reverse sorted, all duplicates — the same three sweeps, the same cost. There is no adversarial input that degrades counting sort in time; the only thing that can hurt it is a key range it was never suited for.

What it is not

It is not in-place in the record-carrying form (it needs an n-sized output buffer plus k counters), it does not work on keys you can only compare rather than index, and it is not "linear time, always" — it is linear in n + k, and the second term is the one that decides whether you may use it.

## The idea Every comparison-based sort discovers order by asking "is this key smaller than that one?". Counting sort never asks. It assumes the keys are small non-negative integers (or can be mapped to them), and exploits the fact that the slots of an array are *already* in order: if you can turn a key into an index, you can turn a bag of keys into a sorted sequence by arithmetic alone. A concrete setting: an image-processing stage holds one record per detected pixel region, each carrying an 8-bit average-luminance key in `0..255` plus a payload (region id, bounding box). Here `n` can be tens of millions while `k`, the size of the key range, is fixed at 256. ## The three passes **Pass 1 — histogram.** Zero a `count` array of size `k`, then sweep the input once: `count[key(a[i])] += 1`. Now `count[v]` is how many records carry luminance `v`. This pass is O(n); the zeroing is O(k). **Pass 2 — prefix sums.** Sweep `count` left to right accumulating: `count[v] += count[v-1]`. The array no longer holds frequencies; `count[v]` is now the number of keys **less than or equal to** `v`. Read as an address, that is the exclusive end of value `v`'s block in the sorted output: all records with luminance `v` occupy the slots `[count[v-1], count[v])`. This is the step candidates skip, and skipping it is why they cannot say where a record goes. It costs O(k). **Pass 3 — placement.** Walk the input, and for each record with key `v` decrement `count[v]` and write the record at the resulting index. Each block fills from its last slot toward its first, so after n writes every record sits in its own slot with its payload intact. This pass is O(n). Total: O(n + k) time, O(n + k) space — `n` for the output buffer, `k` for the counters. ## Why not just re-emit the counts? There is a shorter variant: after the histogram, walk `v` from `0` to `k-1` and write value `v` out `count[v]` times, overwriting the input. It is in-place and needs no output buffer, and it is a perfectly good way to sort a bare array of small integers. It is also useless the moment a key has a payload attached — the region id, the bounding box, the timestamp — because re-emitting a key value cannot reconstruct the record it came from. Real inputs are records, which is why the prefix-sum-plus-placement form is the one worth knowing. ## Keys that do not start at zero The algorithm indexes by key, so the key range must be mapped onto `0..k-1`. For sensor readings in `-40..60`, the map is `index = key - min`, with `k = max - min + 1 = 101` counters. Forgetting the offset indexes negatively; sizing the array `max - min` instead of `max - min + 1` loses or corrupts the largest key. Both are boundary bugs, not design flaws: deriving `min` and `max` in one extra O(n) pass is cheap and makes the mapping explicit. ## What the cost model actually says The time is O(n + k), not O(n). Two terms, and each can dominate. For the 256-value luminance case `k` is a small constant and the whole thing is linear in the number of records, which is exactly where counting sort demolishes a comparison sort. The claim collapses when the key range is wide: the counters have to be allocated, zeroed and swept whether or not the input contains a single record with those keys. Being an upper bound on both terms, O(n + k) also says nothing about constants — but here the constants are tiny, since every pass is a straight sweep with no branching on data. One pleasant consequence of never comparing: the running time does not depend on input order at all. Already sorted, reverse sorted, all duplicates — the same three sweeps, the same cost. There is no adversarial input that degrades counting sort in time; the only thing that can hurt it is a key range it was never suited for. ## What it is not It is not in-place in the record-carrying form (it needs an n-sized output buffer plus k counters), it does not work on keys you can only compare rather than index, and it is not "linear time, always" — it is linear in `n + k`, and the second term is the one that decides whether you may use it.

What exactly does count[v] mean after the prefix-sum pass, and how do you get the start of value v's block?
After the accumulation, `count[v]` is the number of keys less than or equal to `v`, which is the exclusive end index of `v`'s block in the output. The block's first slot is `count[v-1]` (zero for `v = 0`). The placement pass never needs the start explicitly: decrementing `count[v]` before each write fills the block backwards from its last slot and naturally stops at `count[v-1]`.
The keys are sensor readings from -40 to 60. What changes?
Only the mapping. Index by `key - min`, so `-40` lands at 0, and size the counters `max - min + 1 = 101`. Forgetting the offset indexes out of bounds on every negative key; sizing them `max - min` silently drops or corrupts the largest reading. If the bounds are not known statically, one extra O(n) pass to find min and max is cheap and makes the assumption explicit rather than implied.
Why is counting sort's running time the same for sorted, reversed and all-duplicate input?
Because no step branches on the relative order of elements. The histogram pass touches each record once, the prefix pass sweeps the counters once, and the placement pass touches each record once, whatever the arrangement. There is no pivot to choose badly and no comparison to short-circuit, so there is no adversarial ordering. The only input property that changes the cost is the width of the key range.

Like a cloakroom that first counts how many coats belong to each size, then chalks the shelf boundaries, so every coat can be put straight on its shelf without holding two coats up against each other.

saying these in an interview costs you the question

Says counting sort compares keys, just fewer times
Skips the prefix-sum pass and cannot place a record
Thinks re-emitting each key value works for records with payloads
Assumes keys must be zero-based and non-negative
Calls it O(n) with no mention of the key range
Believes sorted or reversed input changes its running time

How does counting sort produce sorted output without ever comparing two elements?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The idea

The three passes

Why not just re-emit the counts?

Keys that do not start at zero

What the cost model actually says

What it is not

▾common follow-ups3 questions

▾analogy~20 s

▾red flags6 flags

§ context

▾related questions7 questions

▾related topics4 topics

The idea

The three passes

Why not just re-emit the counts?

Keys that do not start at zero

What the cost model actually says

What it is not

answer

go deeper

context