慢速排序

慢速排序是一種排序演算法。其基於合併排序的分而治之及遞迴的思想，並故意設計使排序過程非常緩慢。慢速排序由Andrei Broder及Jorge Stolfi在1986年發表的論文Pessimal Algorithms and Simplexity Analysis（論文名稱是漸進最優算法及計算複雜性理論的戲仿）中提出。

演算法
慢速排序是一種原地算法的遞迴演算法。

在簡單的虛擬碼中，此演算法可以被表示為：

 procedure slowsort(A, i, j)                           // 排序一個整數或浮點數數列 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)

 以慢速排序法排序前半部的元素（1.1）
 以慢速排序法排序後半部的元素（1.2）
 比較1.1及1.2排序結果的最後一個元素，選擇相對較大的元素放到列表尾端（1.3）
 排除1.3的元素後，將列表剩下的元素以慢速排序法排序（2）

以 Haskell（純函式程式語言）的實現如下：
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)

複雜度
慢速排序的運行時間關係式為 ，
的漸近下限為
 for any 。由於慢速排序漸近下限的時間複雜度不是多項式時間，即使在最好的情況下也比泡沫排序慢。

參考資料 

排序算法
1961年科學
1961年科學