Questions: Linear-Time Sorting: Counting Sort and Radix Sort

Question 1

You have 10 million employee records, each with a department code from 0 to 999. Which algorithm is most efficient for sorting by department code, and why?

• A. Merge sort — it's stable and handles any key type
• B. Quicksort — it's faster in practice than merge sort
• C. Counting sort — the key range is small and no comparisons are needed
• D. Heapsort — it guarantees O(n log n) in all cases

Answer: (C)

With only 1,000 possible values and 10 million records, counting sort runs in O(n + 1000) ≈ O(n) — effectively linear. Merge sort and quicksort cannot beat O(n log n) because they sort by comparison, and the comparison-based lower bound applies to them. This is exactly the scenario where counting sort shines: a small, known key range over a large input.

Question 2

A student argues that radix sort's O(d(n+b)) time complexity means it is always faster than merge sort's O(n log n). What is wrong with this claim?

• A. Radix sort is not stable, which limits its practical use
• B. Radix sort requires O(n²) auxiliary space
• C. d can be large enough that d(n+b) exceeds n log n, and radix sort only works on keys with a known, finite structure — unlike merge sort
• D. Radix sort's average case degrades to O(n log n), matching merge sort

Answer: (C)

The student ignores two things. First, for large keys with many digit positions, d can be large enough that d(n+b) exceeds n log n. Second, and more fundamentally, radix sort only works on keys with a known, finite structure (integers, fixed-length strings). Merge sort works on any type with a comparator. When the key constraints are met and d is small, radix sort wins; when they aren't, it can't be applied at all.

Question 3

Counting sort and radix sort can achieve linear time only because they do not sort by comparing pairs of elements.

• T. True
• F. False

Answer: True

True. The Ω(n log n) lower bound applies exclusively to comparison-based algorithms — any algorithm that determines order solely through pairwise comparisons requires at least n log n comparisons in the worst case. By counting occurrences or processing digit positions, counting sort and radix sort sidestep comparisons entirely and bypass the lower bound. The tradeoff is that they require structured, bounded keys.

Question 4

Radix sort achieves correct results by sorting from the most significant digit to the least significant digit.

• T. True
• F. False

Answer: False

False. Radix sort must process digits from least significant to most significant (LSD-first). Starting from the most significant digit would require a complex recursive or multiway partition approach. LSD-first works because each pass uses a stable sort: when you sort by a more significant digit, elements sharing the same value at that digit retain their relative order from the prior pass on the less significant digit — preserving the work already done.

Question 5

Why is stability a requirement for radix sort to produce correct results?

Model answer: Radix sort processes one digit at a time from least to most significant. After each pass, elements with the same value at the current digit position must retain their relative order from the previous pass (which established ordering by a less significant digit). If the subroutine were unstable, it would randomly reorder ties, destroying the ordering built up by prior passes. The final result would reflect only the most significant digit, ignoring all less significant digits.

Stability is the mechanism that carries ordering information across passes. Each pass adds one digit's worth of ordering while preserving all prior ordering for ties. Without stability, each pass overwrites rather than refines — the multi-pass structure collapses.