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 / i

Assume $1\le i\le n$. Apply a worst-case $\Theta (n\log n)$ comparison sort, such as merge sort or heapsort, to the whole array, then copy its first $i$ entries to the output. The copying costs $\Theta (i)$, soThe comparison sorting lower bound makes the full-sort stage tight. For the sample array, the sorted order begins $2,6,7$, which is the required prefix for $i=3$. This method spends time ordering all $n-i$ unreported elements as well.