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^[1] (a parody of optimal algorithms and complexity analysis).

Algorithm

Slowsort is a recursive algorithm. It finds the maximum of the sorted array, places that maximum at the end and sorts the remaining array recursively.

An in-place implementation in pseudo code:

 procedure slowsort(A,i,j)                            // sorts Array A[i],...,A[j]
   if i >= j then return
   m := ⌊(i+j)/2⌋                            
   slowsort(A,i,m)                                    // (1.1)
   slowsort(A,m+1,j)                                  // (1.2)
   if A[j] < A[m] then swap A[j] and A[m]             // (1.3)
   slowsort(A,i,j-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)
• Recursively sort the entire list without the maximum in 1.3 (2).

An implementation in Haskell (purely functional) may look as follows.

 slowsort :: Ord a => [a] -> [a]
 slowsort xs
   | length xs <= 1 = xs
   | otherwise      = slowsort xsnew ++ [max llast rlast]  -- (2)
     where  
       l     = slowsort $ take m xs  -- (1.1)
       r     = slowsort $ drop m xs  -- (1.2)
       llast = last l
       rlast = last r
       xsnew = init l ++ min llast rlast : init r
       m     = fst (divMod (length xs) 2)

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