digplanet beta 1: Athena
Share digplanet:

Agriculture

Applied sciences

Arts

Belief

Chronology

Culture

Education

Environment

Geography

Health

History

Humanities

Language

Law

Life

Mathematics

Nature

People

Politics

Science

Society

Technology

Class Visualization of Stooge sort. Sorting algorithm Array O(nlog 3 /log 1.5) O(n)

Stooge sort is a recursive sorting algorithm with a time complexity of O(nlog 3 / log 1.5 ) = O(n2.7095...). The running time of the algorithm is thus slower compared to efficient sorting algorithms, such as Merge sort, and is even slower than Bubble sort, a canonical example of a fairly inefficient and simple sort.

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 list, 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

It is important to get the integer sort size used in the recursive calls by rounding the 2/3 upwards, e.g. rounding 2/3 of 5 should give 4 rather than 3, as otherwise the sort can fail on certain data. However, if the code is written to end on a base case of size 1, rather than terminating on either size 1 or size 2, rounding the 2/3 of 2 upwards gives an infinite number of calls.

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

## Implementation

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

## References

We're sorry, but there's no news about "Stooge sort" right now.

 Limit to books that you can completely read online Include partial books (book previews) .gsc-branding { display:block; }

Oops, we seem to be having trouble contacting Twitter