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:
  • Sort the initial 2/3 of the list
  • Sort the final 2/3 of the list
  • 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.

[edit] Implementation

algorithm stoogesort(L, i = 0, j = |L|-1)
    if Lj < Li then
        Li ↔ Lj
    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

[edit] External links

• Everything2.com - Stooge sort
• Sorting Algorithms (including StoogeSort)