= Solution
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 is
$$
S(n)\leq S(\lceil n/5\rceil)+S(7n/10+O(1))+O(n)=O(n).
$$
Selection and partitioning cost $\Theta(n)$, and sorting the retained prefix costs $\Theta(i\log i)$ for $i\geq2$. Including output at $i=1$ gives
$$
\boxed{T_3(n,i)=\Theta(n+i\log(i+1)).}
$$
Scanning 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.
Back to article page
