Stooge sort is a

recursive Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathemati ...

sorting algorithm In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is importan ...

. It is notable for its exceptionally bad

time complexity In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

of . The running time of the algorithm is thus slower compared to reasonable sorting algorithms, and is slower than

bubble sort Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed. These passes ...

, a canonical example of a fairly inefficient sort. It is however more efficient than Slowsort. The name comes from

The Three Stooges The Three Stooges were an American vaudeville and comedy team active from 1922 until 1970, best remembered for their 190 short subject films by Columbia Pictures. Their hallmark styles were physical farce and slapstick. Six Stooges appear ...

. The algorithm is defined as follows: * If the value at the start is larger than the value at the end, 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 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.

Implementation

function stoogesort(array L, i = 0, j = length(L)-1) -- Not the best but equal to above stoogesort :: (Ord a) => -> stoogesort [] = [] stoogesort src = innerStoogesort src 0 ((length src) - 1) innerStoogesort :: (Ord a) => -> Int -> Int -> innerStoogesort src i j , (j - i + 1) > 2 = src' , otherwise = src' where src' = swap src i j -- need every call t = floor (fromIntegral (j - i + 1) / 3.0) src'' = innerStoogesort src' i (j - t) src = innerStoogesort src'' (i + t) j src' = innerStoogesort src i (j - t) swap :: (Ord a) => -> Int -> Int -> swap src i j , a > b = replaceAt (replaceAt src j a) i b , otherwise = src where a = src !! i b = src !! j replaceAt :: -> Int -> a -> replaceAt (x:xs) index value , index

0 = value : xs , otherwise = x : replaceAt xs (index - 1) value

References

Sources

* *

External links

Sorting Algorithms (including Stooge sort)
Sorting algorithms Comparison sorts Articles with example pseudocode {{comp-sci-stub