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

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

Он может быть описан следующим образом:

1.1. Рекурсивно отсортировать первую половину.

1.2. Рекурсивно отсортировать вторую половину.

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

2. Рекурсивно отсортировать весь массив, кроме максимума.

На псевдокоде он реализуется следующим образом:

подпрограмма slowsort(A, i, j)                      // сортирует массив A[i], ..., A[j]
    если (i >= j) то вернуться
    m := floor((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)

Возможная реализация на 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}$. Медленная сортировка не в полиномиальном времени. Даже в лучшем случае она хуже сортировки пузырьком.

В статье есть список источников, но не хватает сносок.

Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения без сносок могут быть удалены. (18 декабря 2023)