Counting Sort

Question 1

When is Counting Sort most efficient?

Accepted Answer

When k (range) ≈ n or k << n — Counting Sort is efficient when the range of values (k) is comparable to or smaller than n.

Question 2

What is counting sort's time complexity for n elements with keys in range [0, k]?

Accepted Answer

O(n + k) — It counts occurrences in O(n), builds prefix positions in O(k), and places elements in O(n): total O(n + k) — linear when k = O(n).

Question 3

Counting sort beats the Ω(n log n) comparison lower bound because it…

Accepted Answer

It is not a comparison sort — The Ω(n log n) bound applies only to comparison sorts. Counting sort uses keys directly as array indices, sidestepping that bound.

Question 4

What is counting sort's space complexity?

Accepted Answer

A space cost of O(n + k) — It needs a count array of size k and an output array of size n, so O(n + k) auxiliary space — it is not in place.

Question 5

Counting sort is STABLE if elements are placed by…

Accepted Answer

Iterating backward via cumulative count — Iterating the input from the end and decrementing each key's cumulative count preserves the original relative order of equal keys — required for use as a radix-sort subroutine.

Question 6

Counting sort is a poor choice when…

Accepted Answer

When the key range is huge — Space and time scale with k. If k ≫ n (huge or sparse key space), the count array is enormous and wasteful — radix or comparison sorts are better.

Question 7

The role of the CUMULATIVE (prefix) sum over the count array is to…

Accepted Answer

Mark each key's output position — Prefix-summing the counts converts 'how many of each value' into 'where each value's block ends', giving each element its exact output position.

Question 8

To sort integers that include NEGATIVE values with counting sort, you…

Accepted Answer

Offset all keys by −min — Shift every key by subtracting the minimum (adding |min|) so the smallest maps to index 0; subtract the offset back when reading out.

Question 9

Counting sort is most useful as a building block for which algorithm?

Accepted Answer

Radix sort — Radix sort applies a stable counting sort on each digit/byte; counting sort's stability and O(n+k) per pass are exactly what radix needs.

Question 10

Why must counting sort's subroutine be STABLE for radix sort to work?

Accepted Answer

Prior digit order is preserved — LSD radix sort relies on each digit pass keeping the relative order established by previous passes; an unstable sort would scramble that, breaking correctness.

Sort without comparing

Test your knowledge

When is Counting Sort most efficient?

The short version

In more depth

Three Phases

Stability

Limitations

When to reach for this

Interview Questions

References & Further Reading

Related topics

Love this visualization?