Slowsort


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. It was published in 1984 by Andrei Broder and Jorge Stolfi in their paper "Pessimal Algorithms and Simplexity Analysis".

Algorithm

Slowsort is a recursive algorithm.
A pseudocode implementation is given below:

procedure slowsort // Sort array range A in-place.
if start_idx ≥ end_idx then
return
middle_idx := floor
slowsort //
slowsort //
if A < A then
swap //
slowsort //

  • Sort the first half, recursively.
  • Sort the second half, recursively.
  • 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.
  • Sort the entire list, recursively.
An unoptimized implementation in Haskell may look as follows:

slowsort :: => ->
slowsort xs
| length xs <= 1 = xs
| otherwise = slowsort xs' ++ --
where m = length xs `div` 2
l = slowsort $ take m xs --
r = slowsort $ drop m xs --
llast = last l
rlast = last r
xs' = init l ++ min llast rlast : init r

Complexity Analysis

The time complexity of Slowsort is given by the function. It can be found by creating a recurrence relation of the initial recursive calls and respectively and summing the final recursive call and modelling the other operations as a constant in this case. This gives a lower asymptotic bound for, which in Landau notation is given as for any. Therefore Slowsort is not in polynomial time.