Slowsort


Slowsort is a sorting algorithm. It is of humorous nature and not useful. It's based on the principle of multiply and surrender, a tongue-in-cheek joke of divide and conquer. It was published in 1986 by Andrei Broder and Jorge Stolfi in their paper Pessimal Algorithms and Simplexity Analysis.

Algorithm

Slowsort is a recursive algorithm.
An in-place implementation in pseudo code:
procedure slowsort // sorts Array A,...,A
if i ≥ j then
return
m := ⌊ / 2⌋
slowsort //
slowsort //
if A < A then
swap A and A //
slowsort //
An implementation in Haskell may look as follows.

slowsort :: Ord a => ->
slowsort xs
| length xs <= 1 = xs
| otherwise = slowsort xsnew ++ --
where
l = slowsort $ take m xs --
r = slowsort $ drop m xs --
llast = last l
rlast = last r
xsnew = init l ++ min llast rlast : init r
m = fst

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.