Questions: Counting Sort Algorithm

Question 1

What is the time complexity of counting sort when sorting n integers drawn from the range [0, k−1]?

• A. O(n log n) — same as comparison-based sorts like merge sort
• B. O(n + k) — one pass over the input plus one pass over the count array
• C. O(n × k) — each element is compared against all k possible values
• D. O(k log k) — the count array itself must be sorted

Answer: (B)

Counting sort makes one pass over the n input elements to build the frequency array (O(n)), one pass of length k to compute prefix sums (O(k)), and one final pass over the n input elements to place them (O(n)). Total: O(n + k). There are no comparisons between elements at all — the algorithm uses value-as-index arithmetic. This is how it beats the O(n log n) lower bound that applies only to comparison sorts.

Question 2

You need to sort 1,000 integers where each value can range from 0 to 1,000,000,000. Would counting sort be the best approach?

• A. Yes — counting sort is always faster than comparison sorts since O(n + k) beats O(n log n)
• B. No — with k = 10^9 and only n = 1,000 elements, the count array would require a billion entries, making counting sort far less practical than a comparison sort
• C. Yes — as long as the values are integers, counting sort outperforms merge sort regardless of range
• D. It depends only on whether the array is nearly sorted; counting sort is best for nearly-sorted inputs

Answer: (B)

Counting sort's O(n + k) time and O(k) space are only practical when k is on the order of n. With n = 1,000 and k = 10^9, allocating and traversing a billion-element count array dwarfs any savings from avoiding comparisons. In this case, merge sort's O(n log n) ≈ O(10,000) operations on 1,000 elements is vastly more efficient. Option A is the key misconception: 'O(n + k) beats O(n log n)' is only true when k = O(n).

Question 3

Counting sort avoids the O(n log n) comparison-sort lower bound by making fewer comparisons than merge sort — it simply compares elements more cleverly.

• T. True
• F. False

Answer: False

Counting sort makes zero comparisons between elements. It bypasses the comparison lower bound entirely by using a fundamentally different mechanism: it uses each element's value as an index into the count array, then uses arithmetic (prefix sums) to determine output positions. The O(n log n) lower bound applies only to algorithms that determine order exclusively through element comparisons — counting sort doesn't fall in that category at all.

Question 4

Counting sort is a stable sorting algorithm, meaning elements with equal keys appear in the output in the same relative order they had in the input.

• T. True
• F. False

Answer: True

Stability is achieved by scanning the input array from right to left during the placement step. The last occurrence of a given value v is placed at the highest available position for v, the second-to-last at the next position down, and so on. This preserves original relative ordering among equal elements. Stability is not incidental — it is deliberately engineered and is essential for counting sort's role as a subroutine in radix sort, where the relative order established by one digit pass must be preserved in the next.

Question 5

Explain why counting sort can sort n elements faster than O(n log n) in some cases, but cannot universally replace comparison-based sorting algorithms.

Model answer: Counting sort avoids comparisons entirely by using element values as array indices — a trick that only works when values are integers in a known, bounded range [0, k−1]. Its O(n + k) time is better than O(n log n) when k is small relative to n, because the algorithm's work is proportional to the size of the value range, not the number of comparisons needed to establish order. However, if k is large (say, 10^9 for n = 1,000 elements), the O(k) cost to initialize and scan the count array dominates and makes counting sort impractical. Additionally, counting sort cannot handle non-integer keys (floating-point numbers, strings, arbitrary objects) because those cannot serve as array indices. Comparison sorts work on any ordered type regardless of range.

The tradeoff is essentially: counting sort trades the O(n log n) comparison cost for O(k) space and time, which only benefits you when k is manageable. This is why counting sort appears most often as a building block (e.g., in radix sort on digit-by-digit passes) where k is small by construction.