Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 6 / c / iii

Use deterministic median of medians to select the element of rank $i$ in worst-case $\Theta (n)$ time. Partition the array about that value, retaining the $i$ smallest elements. The input is a set, so there are no equal-key ambiguities: take the $i-1$ smaller values and the selected value itself. Sort these $i$ elements with merge sort, then output them.

For completeness, median of medians groups values in fives, finds each small group's median, recursively selects a median of those medians as a pivot, and recurses only into the partition containing the requested rank. At least $3n/10-O(1)$ entries lie on each side of the pivot. Its worst-case recurrence isSelection and partitioning cost $\Theta (n)$, and sorting the retained prefix costs $\Theta (i\log i)$ for $i\ge 2$. Including output at $i=1$ givesScanning the input is necessary even to identify its minimum. Ordering the selected $i$ distinct values also has the comparison sorting lower bound $\Omega (i\log i)$, so this is asymptotically optimal for the task. A usual randomized Quickselect gives linear expected selection time, but its quadratic worst case would not establish the requested worst-case guarantee.