慢速排序

慢速排序（）是一種排序演算法。其基於合併排序的分而治之及遞迴的思想，並故意設計使排序過程非常緩慢。慢速排序由安德烈·布羅德（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]
slowsort :: Ord a => [a] -> [a]
slowsort xs
| length xs

複雜度
慢速排序的運行時間關係式為 T(n) = 2 T(n/2) + T(n-1) + 1 ，
T(n) 的漸近下限為
\Omega\left(n^{ \frac{\log_2(n)}{(2+\epsilon)}}\right) for any \epsilon > 0 。由於慢速排序漸近下限的時間複雜度不是多項式時間，即使在最好的情況下也比冒泡排序慢。

參考資料