- Stooge sort
Infobox Algorithm
class=Sorting algorithm
data=Array
time = O("n"log(3)/log(1.5))
space = O("n")
optimal=NoStooge 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 running time of the algorithm is thus extremely slow compared to efficient sorting algorithms, such asMerge 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 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 procedureThe algorithm gets its name from
slapstick routines of theThree Stooges , in which each stooge hits the other two.Fact|date=July 2007Implementation
External links
* [http://www.everything2.com/index.pl?node=stooge%20sort Everything2.com - Stooge sort]
* [http://cg.scs.carleton.ca/~morin/misc/sortalg/ Sorting Algorithms (including StoogeSort)]References
*Paul E. Black, "stooge sort", in Dictionary of Algorithms and Data Structures (online), Paul E. Black, ed., U.S. National Institute of Standards and Technology. Accessed 3 September 2008. Available from: [http://www.nist.gov/dads/HTML/stoogesort.html www.nist.gov/dads/HTML/stoogesort.html]
Wikimedia Foundation. 2010.