A stooge sort
) is an overly clever method of sorting
a list of elements.
- Compare the first and last elements in the list, and swap them if they are out of order.
- Recursively sort the first two-thirds of the list.
- Recursively sort the last two-thirds of the list.
- Recursively sort the first two-thirds of the list again.
itself is rather elegant
, with only four steps involved. But you've got to figure there's a reason why it's named after Curly, Moe, and Larry
. In fact, this problem is often used in introductory algorithms classes. The question is: how good is it? Can it compare to the fast sorting algorithms
, merge sort
, or heapsort
It should be clear that the time complexity of the algorithm is proportional to T(n)=3T(2n/3)+1. It turns out that this is actually about O(n2.71) (the master theorem/master method is helpful in determining this). Thus the sort is incredibly poor - far worse even than insertion sort, selection sort, and the venerable bubble sort.