慢速排序

procedure slowsort(A, i, j)                           // 排序一個整數或浮點數數列 A,...,A ，若要使用其他的資料類型則必須重載大於或小於運算符    if i ≥ j then        return    m := ⌊(i+j) / 2⌋                                slowsort(A, i, m)                                 // (1.1)    slowsort(A, m+1, j)                               // (1.2)    if A < A then        swap A and A                            // (1.3)    slowsort(A, i, j-1)                               // (2)

slowsort :: Ord a =>  -> slowsort xs  | length xs <= 1 = xs  | otherwise      = slowsort xsnew ++   -- (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)

复杂度

慢速排序的运行时间关系式为 ${\displaystyle T(n)=2T(n/2)+T(n-<!--\; -\; -->1)+1}$，${\displaystyle T(n)}$的渐近下限为${\displaystyle \mathrm{\Omega <!--\; \Omega \; -->}\left(n^{\frac{{\log }_2<!--\; \; -->(n)}{(2+\mathrm{ϵ<!--\; ϵ\; -->})}}\right)}$ for any ${\displaystyle \mathrm{ϵ<!--\; ϵ\; -->}>0}$。由于慢速排序渐近下限的时间复杂度不是多项式时间，即使在最好的情况下也比泡沫排序慢。