= Solution
\b[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\ldots})$, 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.
Back to article page
