Slowsort

For the other sorting algorithm also known as "slowsort", see Bogosort.

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

Algorithm

Slowsort is a recursive algorithm.

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 $T(n)$ for Slowsort is $T(n)=2T(n/2)+T(n-1)+1$. A lower asymptotic bound for $T(n)$ in Landau notation is $\Omega \left(n^{\frac {\log _{2}(n)}{(2+\epsilon )}}\right)$ for any $\epsilon >0$. Slowsort is therefore not in polynomial time. Even the best case is worse than Bubble sort.