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. | 
