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 / d / Solution

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.