Slowsort

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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[edit]

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[edit]

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[edit]

  1. ^ "CiteSeerX — Pessimal Algorithms and Simplexity Analysis". CiteSeerX 10.1.1.116.9158. Cite journal requires |journal= (help)