Stooge sort

From Wikipedia, the free encyclopedia

Stooge sort is a recursive sorting algorithm with a time complexity of about O(n^2.7). The exponent's exact value is log(3) / log(1.5) = 2.709...

The algorithm is defined as follows:

If the value at the end is smaller than the value at the start, swap them.
If there are 3 or more elements in the current list subset,
then:
- Stooge sort the initial 2/3 of the list
- Stooge sort the final 2/3 of the list
- Stooge sort the initial 2/3 of the list again
else: exit the procedure

The algorithm gets its name from slapstick routines of the Three Stooges, in which each stooge hits the other two.^{[citation needed]}

[edit] Implementation

algorithm stoogesort(array L, i = 0, j = length(L)-1)
     if L[j] < L[i] then
         L[i] ↔ L[j]
     if j - i > 1 then
         t = (j - i + 1)/3
         stoogesort(L, i  , j-t)
         stoogesort(L, i+t, j  )
         stoogesort(L, i  , j-t)
     return L