Медленная сортировка

Медленная сортировка — рекурсивный алгоритм. На псевдокоде он имплементируется таким образом:

 Подпрограмма slowsort(A,i,j)                            // сортирует Массив A[i],...,A[j]
   если i >= j то вернуться
   m := ⌊(i+j)/2⌋                            
   slowsort(A,i,m)                                    // (1.1)
   slowsort(A,m+1,j)                                  // (1.2)
   если A[j] < A[m] то поменять A[j] и A[m]             // (1.3)
   slowsort(A,i,j-1)                                  // (2)

• Рекурсивно отсортировать первую половину (1.1)
• Рекурсивно отсортировать вторую половину (1.2)
• Найти максимум всего массива, сравнивая результаты 1.1 и 1.2, и поместить его в конец массива (1.3)
• Рекурсивно отсортировать весь массив, кроме максимума

Возможная имплементация на 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)

Время выполнения ${\displaystyle T(n)}$ медленной сортировки равно ${\displaystyle T(n)=2T(n/2)+T(n-1)+1}$. Медленная сортировка не в полиномиальном времени. Даже в лучшем случае она хуже сортировки пузырьком.