Slowsort
Appearance
Slowsort is a sorting algorithm. It is of humorous nature and not useful. It is a reluctant algorithm based on the principle of multiply and surrender (a parody formed by taking the opposites of divide and conquer). It was published in 1986 by Andrei Broder and Jorge Stolfi in their paper Pessimal Algorithms and Simplexity Analysis[1] (a parody of optimal algorithms and complexity analysis).
Algorithm
Slowsort is a recursive algorithm.
- It sorts in-place.
- It is a stable sort. (It does not change the order of equal-valued keys.)
This is an implementation in pseudocode:
procedure slowsort(A[], start_idx, end_idx) // Sort array range A[start ... end] in-place.
if start_idx ≥ end_idx then
return
middle_idx := floor( (start_idx + end_idx)/2 )
slowsort(A, start_idx, middle_idx) // (1.1)
slowsort(A, middle_idx + 1, end_idx) // (1.2)
if A[end_idx] < A[middle_idx] then
swap (A[end_idx] , A[middle_idx]) // (1.3)
slowsort(A, start_idx, end_idx - 1) // (2)
- Sort the first half, recursively. (1.1)
- Sort the second half, recursively. (1.2)
- Find the maximum of the whole array by comparing the results of 1.1 and 1.2, and place it at the end of the list. (1.3)
- Sort the entire list (except for the maximum now at the end), recursively. (2)
An unoptimized implementation in Haskell (purely functional) may look as follows:
slowsort :: (Ord a) => [a] -> [a]
slowsort xs
| length xs <= 1 = xs
| otherwise = slowsort xs' ++ [max llast rlast] -- (2)
where m = length xs `div` 2
l = slowsort $ take m xs -- (1.1)
r = slowsort $ drop m xs -- (1.2)
llast = last l
rlast = last r
xs' = init l ++ min llast rlast : init r
Complexity
The runtime for Slowsort is .
A lower asymptotic bound for in Landau notation is for any .
Slowsort is therefore not in polynomial time. Even the best case is worse than Bubble sort.
References
- ^ Andrei Broder; Jorge Stolfi (1984). "Pessimal Algorithms and Simplexity Analysis" (PDF). ACM SIGACT News. 16 (3): 49–53. CiteSeerX 10.1.1.116.9158. doi:10.1145/990534.990536. S2CID 6566140.