A
stooge sort (or
stoogesort) 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.
The
algorithm 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 like
quicksort,
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.