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

Медленная сортировка (англ. Slowsort) — непрактичный и юмористический алгоритм сортировки. Он основан на принципе размножай и сдавайся (англ. multiply and surrender), пародии на разделяй и властвуй. Его опубликовали Андрей Бродер и Йорге Столфи в 1986 году в своей статье Pessimal Algorithms and Simplexity Analysis (Пессимальные алгоритмы и анализ простоты, пародия на оптимальные алгоритмы и анализ сложности).

Алгоритм

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

 Подпрограмма 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)

Сложность

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