Stooge sort


Stooge sort is a recursive sorting algorithm. It is notable for its exceptionally bad time complexity of.
The running time of the algorithm is thus slower compared
to reasonable sorting algorithms, and is slower than Bubble sort, a canonical example of a fairly inefficient sort.
It is however more efficient than Slowsort.
The name comes from The Three Stooges.
The algorithm is defined as follows:
It is important to get the integer sort size used in the recursive calls by rounding the 2/3 upwards, e.g. rounding 2/3 of 5 should give 4 rather than 3, as otherwise the sort can fail on certain data. However, if the code is written to end on a base case of size 1, rather than terminating on either size 1 or size 2, rounding the 2/3 of 2 upwards gives an infinite number of calls.

Implementation


function stoogesort