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

For heapsort, use the usual array representation of a max-heap, indexed from zero, with children $2i+1,2i+2$. Build the max-heap from the last internal node towards the root, using heapify down. The three build stages are

start                    [2,7,3,2,8,1]
sift at index 2          [2,7,3,2,8,1]
sift at index 1          [2,8,3,2,7,1]
sift at index 0          [8,7,3,2,2,1]

At index zero, the value 2 moves below 8 and then below 7. Next exchange the root with the last active element, shorten the active heap, and restore heap order. A vertical separator below distinguishes the active prefix from its sorted final suffix.

The trace chooses the left child when equal children tie; other tie conventions can give different intermediate heaps with the same sorted output.

For quicksort, use the head as pivot and partition the remaining elements into those strictly less than it and those greater than or equal to it, retaining their order within each partition. This specifies how the duplicate 2 is handled:

pivot 2:  [1]       | 2 | [7,3,2,8]
pivot 7:  [3,2]     | 7 | [8]
pivot 3:  [2]       | 3 | []

Empty and singleton lists are already sorted. Returning from the recursive calls gives

Q [3,2]       = [2] ++ [3] ++ []       = [2,3]
Q [7,3,2,8]   = [2,3] ++ [7] ++ [8]   = [2,3,7,8]
Q [2,7,3,2,8,1] = [1] ++ [2] ++ [2,3,7,8]

For counting sort, count keys $1$ through $8$. After reading each input key, the count vector is

initial: (0,0,0,0,0,0,0,0)
read 2:  (0,1,0,0,0,0,0,0)
read 7:  (0,1,0,0,0,0,1,0)
read 3:  (0,1,1,0,0,0,1,0)
read 2:  (0,2,1,0,0,0,1,0)
read 8:  (0,2,1,0,0,0,1,1)
read 1:  (1,2,1,0,0,0,1,1)

The cumulative counts are $(1,3,4,4,4,4,5,6)$. For the usual stable sorting version with zero-based output indices, scan the input from right to left, place a key $k$ at position $C[k]-1$, and decrement $C[k]$. The successive placements are 1 at $0$, 8 at $5$, the later 2 at $2$, 3 at $3$, 7 at $4$, and the earlier 2 at $1$. The final answer for all three sorting algorithms is

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.