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

Divide-and-conquer algorithms split a problem into smaller instances of the same kind, solve them recursively, and combine the solutions. A base case handles instances too small to split. For merge sort, divide the input into two halves, recursively sort both halves, and merge them by repeatedly taking the smaller current head. Empty and singleton inputs are already sorted.

The merge algorithm step preserves sortedness because its chosen head is no larger than either remaining head; it also preserves every input occurrence. These facts and mathematical induction on input length prove correctness. Splitting and merging take $\Theta (n)$ time, soAt each level the subproblem sizes sum to $n$, and there are $\Theta (\log n)$ levels. Part 3(c) supplies an explicit Haskell implementation of this construction with a more specialized comparison rule. Standard array implementations use $O(n)$ auxiliary storage.

Restrict attention to distinct keys; any comparison sort must handle these inputs. A deterministic comparison sort can be represented by a binary decision tree: an internal node records a comparison and its two possible outcomes, and a leaf records the final ordering of the input positions.

There are $n!$ possible relative orders. Two different orders cannot finish at the same leaf, since the algorithm would then output the same ordering of positions for both, making at least one result incorrect. A binary decision tree of height $h$ has at most $2^h$ leaves. HenceUsing the given bound, or just the last $\lfloor n/2\rfloor$ factors of $n!$, givesThis is a worst-case comparison sorting lower bound, and merge sort achieves the same order. The result concerns comparison sorting; a procedure that uses numerical digits or bounded integer values has a different computational model.

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.

Store the array as a binary heap with min-heap order. Build it bottom-up by sifting down internal nodes in reverse order, rather than inserting all $n$ values one at a time. The sum of subtree heights is $O(n)$, so construction costs $\Theta (n)$. Then perform $i$ minimum extractions: output the root, move the last remaining entry to the root, and sift it down to restore the heap order.

Each extraction returns the smallest remaining key, so the outputs are the $i$ smallest keys in increasing order. For a heap of current size $s$, an extraction takes $O(\log (s+1))$ time. HenceThe tight worst-case bound for this ordinary binary heap implementation isWhen the extraction term is substantial, worst-case extractions follow root-to-leaf paths of logarithmic length; when $i$ is small, the linear construction already dominates. The bound stays valid at $i=n$, since $\log (n!)=\Theta (n\log n)$. Building by $n$ separate insertions would lose the linear construction bound and is unnecessary.

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.