Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 5 / b

Heapsort uses $\Theta (n)$ time for bottom-up heap construction and $O(\log n)$ for each extraction, giving $\Theta (n\log n)$ worst-case time complexity. An iterative heapify down on an array uses $O(1)$ auxiliary space complexity. Ordinary heapsort is not a stable sorting method.

Quicksort has balanced-case and average-case $\Theta (n\log n)$ time complexity when the input order supplies suitably distributed pivot ranks. With the prescribed first-element pivot, sorted inputs produce subproblems of sizes $0$ and $n-1$, giving $T(n)=T(n-1)+\Theta (n)=\Theta (n^2)$. With the stated two-way partition convention, all-equal keys also give this worst case. There is no input-independent expected bound without a distribution or randomization assumption. For an in-place array implementation, the recursion stack is $O(\log n)$ when balanced and $O(n)$ in the worst case; the functional list trace also allocates new partition spines and copied concatenation prefixes. Ordinary in-place quicksort is not stable sorting; the stable-partition list convention used in the trace can preserve equal-key order at additional allocation cost.

Counting sort uses $\Theta (n+k)$ time complexity for $k$ possible consecutive integer keys. The stable sorting version uses $\Theta (n+k)$ auxiliary space complexity including the output array; counting and re-emitting bare keys needs only $O(k)$ beyond its output. It is attractive when $k$ is small, but a sparse huge key range makes both initialization and count storage expensive. It relies on indexing by bounded integer keys, so it is not subject to the comparison sorting lower bound.