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

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

Алгоритм

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

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

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)

Сложность

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