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(n^{2.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.