Stooge sort

From Free net encyclopedia

Stooge sort is a recursive sorting algorithm with a time complexity of about O(n2.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 2 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

Retrieved from "http://www.netipedia.com/index.php/Stooge_sort"