Rapid review: sorting, selection & the lower bound

Which sort, and why (the exam justification)

Exam questions rarely ask 'what is heapsort'; they ask 'given these constraints, which sort and why'. Reason from the constraints:

• Need a worst-case guarantee AND in-place? → Heapsort (Θ(n lg n) worst, Θ(1) space). Merge sort matches the time but needs Θ(n) space; quicksort is in-place but Θ(n²) worst.
• Need stability? → Merge sort (or counting/radix). Heapsort and quicksort are not stable.
• Fastest in practice on random data, space-tight? → Quicksort (small constant factors, in-place) — accept the Θ(n²) worst case, or randomize the pivot to make it astronomically unlikely.
• Nearly-sorted or tiny input? → Insertion sort (Θ(n) best case; this is why Timsort uses it for small runs).
• Keys are small integers / bounded range k? → Counting sort Θ(n+k), or radix for larger keys; both beat the comparison lower bound.
• External / linked data? → Merge sort (sequential access, no random indexing needed).

The Ω(n lg n) comparison-sort lower bound (reconstruct this argument)

Any comparison sort is modeled as a decision tree: each internal node is a comparison $a_i\lessgtr a_j$, each leaf a permutation. To sort correctly, every one of the $n!$ input permutations must reach its own leaf — so the tree has $\ge n!$ leaves. A binary tree of height $h$ has $\le 2^h$ leaves, so

$$2^h\ge n!\Rightarrow h\ge \lg (n!)=\Theta (n\lg n),$$

using Stirling's $\lg (n!)=\Theta (n\lg n)$. The height is the worst-case number of comparisons, so every comparison sort makes $\Omega (n\lg n)$ comparisons in the worst case — merge sort and heapsort are asymptotically optimal. This bound is model-specific: it applies only to sorts whose sole operation is comparing elements.

How linear-time sorts dodge the bound

Counting, radix, and bucket sort are not comparison sorts — they use the key values (as array indices or digits), so the decision-tree argument does not apply. Counting sort assumes keys in a bounded range $[0,k]$ and is stable (scan right-to-left when scattering); radix sort applies a stable counting sort per digit, LSD first — radix is wrong if its inner sort is not stable.

Selection in linear time

Finding the k-th smallest without fully sorting: RANDOMIZED-SELECT recurses into only one side of a partition, so its expected work is a geometric series $\Theta (n)$ (versus quicksort's two-sided harmonic $\Theta (n\lg n)$). For a worst-case Θ(n) guarantee, median-of-medians picks the pivot deterministically from medians of groups of 5 — groups of 5 (not 3) are what make the two recursive calls sum to $<n$.