Noesis
3.6.6 · D5Sorting & Searching

Question bank — Counting sort — O(n + k), integer keys only

1,396 words6 min read↑ Back to topic

The whole algorithm hangs on three moves: count, prefix-sum, and place-from-the-back. Every trap here is a way one of those three moves gets misunderstood.

True or false — justify

Counting sort makes zero key-to-key comparisons.
True — it uses each key as an array index (count[v] += 1), which is random access, not a comparison; that is exactly why the comparison lower bound does not apply.
Counting sort is always faster than quicksort.
False — it is , so when the key range dwarfs (e.g. 32-bit keys, ) it allocates billions of cells and loses badly; it only wins when .
Counting sort works on any list of numbers.
False — it needs integer keys (or a bijection to small integers) because you cannot use a float or a string directly as an array index.
Counting sort is a stable sort as normally written.
True — placing elements while scanning the input right-to-left and decrementing before writing sends the last equal element to the last slot, preserving original relative order (see Stability in Sorting).
If two elements share a key, counting sort might swap their original order.
False if written correctly — but true if you scan the input left-to-right during placement, which silently reverses equal keys and breaks stability.
The count array should have size .
False — the values are , which is distinct values; size overflows on the maximum key. Use .
After the prefix-sum step, count[v] tells you how many times appears.
False — before prefix sum it does; after prefix sum count[v] = number of elements with key , i.e. the boundary index just past 's block.
Counting sort's time depends on how "shuffled" the input is.
False — it does the same three linear passes regardless of input order; there is no best/worst case split like quicksort has.
You can sort negative integers with counting sort.
True — offset every key by so the range maps to , sort, then add back; the offset is just a shift of array indices.
Counting sort is the engine that makes Radix Sort linear.
True — radix sort runs a stable counting sort per digit; if that per-digit pass weren't stable, higher digits already sorted would get scrambled by lower ones.

Spot the error

"I sized count = [0]*k for keys in and it crashes on the max key — why?"
The maximum key is itself, but index is out of bounds in an array of length ; there are values so you need [0]*(k+1).
"I placed elements scanning A left-to-right and the numbers still came out sorted, so my code is fine."
The ordering by value is correct, but equal keys are now reversed — the sort is no longer stable, and any radix sort built on top will corrupt silently. Scan right-to-left.
"I skipped the prefix-sum step and just wrote each value count[v] times into the output — that's simpler."
That works for plain integers but throws away the elements' identities, so it cannot sort records (pairs, objects) by an integer field, and it loses stability entirely.
"To save memory I let count cover only the values that actually appear."
Then you can no longer index by the key directly; you'd need a hash map, which reintroduces overhead and defeats the indexing that makes counting sort fast — that idea is closer to Bucket Sort.
"I decrement count[v] after writing: out[count[v]] = x; count[v] -= 1."
Off-by-one — count[v] after prefix sum is one past 's last slot, so you must decrement first to land inside the block; writing first overshoots the array or overwrites a neighbour.
"My keys are floats between 0 and 1, so I'll multiply by 1000 and round — same thing."
Rounding is a lossy, non-bijective map: distinct floats can collapse to the same integer, corrupting order. For real-valued keys use Bucket Sort or a comparison sort instead.

Why questions

Why does counting sort escape the comparison lower bound?
That bound counts comparisons in a decision tree; counting sort makes none — it reads the key as an index, so the tree argument simply doesn't describe it.
Why do we scan the input right-to-left in the placement step?
count[v]-1 is the highest free slot for value ; feeding elements from the back means the last equal element claims the last slot, keeping original order → stability.
Why does the prefix sum give us exact final positions?
If elements have key , the last must sit at index ; the cumulative count is precisely that boundary , so count[v]-1 is the correct 0-based slot.
Why must be small for counting sort to be worthwhile?
The count array has size , so both time and space carry a term; when this is linear, but makes it -dominated and memory-hungry.
Why is stability the reason counting sort powers Radix Sort rather than raw speed?
Radix sort sorts one digit at a time from least to most significant; only a stable per-digit sort keeps the previously-sorted lower digits intact, so stability is the load-bearing property, not just a bonus.
Why can't we replace the count array with a comparison-based tally and still call it counting sort?
The defining trick is direct integer indexing; the moment you compare keys you re-enter the comparison model and forfeit the guarantee.

Edge cases

What happens when the input array is empty ()?
All three passes are trivial: tally does nothing, prefix sum still runs over (), placement does nothing, and you return an empty array — correct.
What if every element has the same key?
They all land in that value's block; scanning right-to-left keeps their original order, so the output equals the input — a clean demonstration of stability.
What if the array is already sorted?
Counting sort still does its full three linear passes — it has no "already sorted" fast path, unlike adaptive comparison sorts.
What if is much larger than , say sorting 5 numbers with ?
You allocate ~ cells for just 5 elements; the term dominates and wastes memory — a comparison or radix sort is the right choice here (see Time Complexity / Big-O).
What if a key exceeds the declared range, e.g. a value slips in?
count[k+3] is out of bounds → crash or silent corruption; you must know a correct upper bound, or compute before allocating.
What if all keys are negative, e.g. ?
Offset by to map onto , sort the shifted keys, then subtract back — negativity is just a shifted index range.
What if the range is contiguous but doesn't start at 0, e.g. keys in ?
Same offset trick: subtract the minimum () so indices run , avoiding a wasteful count array of size 106 that's 94% empty.
Recall One-line self-test before you leave

Name the single property that (a) makes counting sort stable and (b) makes it usable inside radix sort. ::: Placing elements while scanning the input right-to-left with pre-decrement, which preserves the original order of equal keys.