Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms (resit) / 8

Build a max-heap, then repeatedly swap its root with the last element of the active prefix, shrink that prefix and restore heap order by heapify down. A zero-based implementation is

for i = floor(n/2)-1,...,0:
    siftDown(A,i,n)
for end = n-1,...,1:
    swap A[0],A[end]
    siftDown(A,0,end)

siftDown(A,i,end) repeatedly exchanges entry i with its larger child while the child lies below end and has a larger key. The suffix beyond end is already sorted and never touched again. For the specified input, key stages of heapsort are

The final array is $[1,2,3,4,5]$. Bottom-up construction takes $O(n)$ time because there are progressively fewer nodes at each greater subtree height; the extractions give worst-case $O(n\log n)$ time and constant auxiliary storage for iterative sifting.

A deterministic comparison sort on $n$ distinct keys must distinguish $n!$ possible initial orders. Its binary comparison decision tree therefore has at least $n!$ leaves: a leaf fixes one output ordering and cannot be correct for two different strict orders of the original records.

A binary tree of height $h$ has at most $2^h$ leaves, henceThis is the comparison sorting lower bound on the worst-case number of comparisons. Distinct keys have only two possible comparison outcomes, even if an implementation's comparator also supports equality. Algorithms exploiting numeric key values, such as counting sort, fall outside this model.

The printed split uses $n$ while naming the current length $m=j-i$. For the intended stooge sort, read that split as $k=\lfloor m/3\rfloor$ at every recursive call. Keeping one fixed original $n$ instead is not the standard algorithm and does not generally sort correctly.

The three recursive calls then each have length $m-\lfloor m/3\rfloor =\lceil 2m/3\rceil$, and all other work is constant. ThusA version of the master theorem sufficient here states: if $T(n)=aT(\lceil n/b\rceil )+f(n)$ with constants $a\ge 1,b>1$, fixed-size base cases and $f(n)=O(n^{{\log }_{b}a-ϵ})$ for some $ϵ>0$, then $T(n)=\Theta (n^{{\log }_{b}a})$, provided the recursive sizes shrink above the base threshold. Apply it with $a=3,b=3/2,f=\Theta (1)$ to obtainThe rounded size is important for correctness; it does not change this asymptotic exponent.

Prefer the alternatives for large unrestricted arrays. Merge sort and heapsort have $O(n\log n)$ worst-case time, while insertion sort has $O(n^2)$ worst-case time and can be much faster on nearly sorted data. The intended stooge sort has worst-case $\Theta (n^{2.7095\dots })$, so even insertion sort has the better worst-case exponent.

The first two give the stronger general asymptotic guarantee. Choices between them can depend on storage and stable sorting requirements; these considerations do not rescue Stooge sort's much larger work count.

No: Stooge sort is not stable. Give equal keys distinct record identities and start withThe initial endpoint swap gives $[1,2_b,2_a]$. The later two-element calls either see increasing keys or equal keys, so they make no swap. The two records with key 2 have reversed their original order, contradicting stable sorting. The example uses length three, where the intended current-length split is unambiguous.