Questions: Sorting Lower Bounds and Non-Comparison Sorts

Question 1

A developer claims to have written a comparison-based sorting algorithm with O(n) worst-case runtime. What does the decision-tree lower bound tell you about this claim?

• A. It's plausible if the algorithm avoids redundant comparisons cleverly
• B. It's impossible — any comparison-based sort requires Ω(n log n) comparisons in the worst case
• C. It's possible only for nearly-sorted inputs
• D. It depends on whether the algorithm is stable or not

Answer: (B)

The decision-tree argument is a proof about the entire *class* of comparison-based algorithms, not any specific implementation. Because there are n! possible orderings of n elements, any correct comparison-based sort needs a decision tree with at least n! leaves, requiring depth at least log₂(n!) = Ω(n log n). No matter how clever the algorithm, if it only uses comparisons, it cannot beat this bound. The developer's claim is mathematically impossible.

Question 2

Why can't counting sort be used to sort arbitrary comparable objects, such as user-defined records sorted by a custom comparator?

• A. Because counting sort is not a stable sorting algorithm
• B. Because counting sort requires knowing the integer key range [0, k] in advance, not just a comparison function
• C. Because counting sort's space complexity makes it impractical for large objects
• D. Because counting sort runs in O(n + k) which is slower than O(n log n) for large n

Answer: (B)

Counting sort bypasses comparisons entirely by using key values as array indices — it counts how many times each integer value appears and places elements directly. This only works when you know the exact integer range [0, k] ahead of time. Arbitrary comparable objects (e.g., strings, custom structs) don't have a bounded integer key you can index into. The algorithm requires explicit numeric keys, not just an abstract ordering relation. This is the structural constraint that makes non-comparison sorts non-general.

Question 3

The Ω(n log n) sorting lower bound proves that no sorting algorithm can run faster than O(n log n) in the worst case.

• T. True
• F. False

Answer: False

The lower bound is conditional — it applies *only* to comparison-based algorithms. Counting sort runs in O(n + k) and radix sort in O(dn), both of which can be linear in n. These algorithms break the barrier by not comparing elements to each other at all; they exploit the structure of the keys (integer values, digit decomposition). The statement as given is a classic overgeneralization of the theorem's scope.

Question 4

The decision-tree argument works because a binary tree of height d has at most 2^d leaves, and a correct sorting algorithm must be able to produce any of the n! permutations of the input.

• T. True
• F. False

Answer: True

Exactly. Each leaf of the decision tree represents one possible sorted output (a permutation). Since the algorithm must handle any input ordering correctly, it needs at least n! leaves. A binary tree of height d has at most 2^d leaves, so 2^d ≥ n!, giving d ≥ log₂(n!) = Ω(n log n). This is the depth — the number of comparisons on the worst-case path — which proves the lower bound on comparisons.

Question 5

Explain why radix sort requires a *stable* sub-sort at each digit position. What goes wrong if an unstable sort is used?

Model answer: Radix sort works by sorting digit by digit from least significant to most significant. At each step, elements with the same digit at the current position must retain the relative order established by previous passes (which captured the less-significant digits). If the sub-sort is unstable, it scrambles the relative order of ties, destroying the ordering information accumulated in previous passes. The final result will be incorrectly sorted.

Concretely: after sorting by the units digit, [12, 32, 21] might become [21, 12, 32]. When we then sort by the tens digit, 1 < 3 puts [12, 21] before [32] — but within the '1x' group, stability preserves [12, 21] in the order from the previous pass. An unstable sort might swap them to [21, 12], giving [21, 12, 32] — wrong. Stability is the mechanism by which each pass respects and preserves the work done by prior passes.