Stooge Sort

Проблема

Многие эффективные сортировки делят массив на непересекающиеся половины или трети и обрабатывают их независимо. Что произойдёт, если вместо непересекающихся частей рекурсивно обрабатывать перекрывающиеся две трети диапазона - сначала первые 2/3, потом последние 2/3, потом снова первые 2/3? Формально это всё ещё корректно сортирует массив, но перекрытие означает огромную избыточную работу: значительная часть элементов обрабатывается заново по несколько раз на каждом уровне рекурсии.

Решение

Для диапазона [lo, hi] сначала сравниваются крайние элементы: если a[lo] больше a[hi], они меняются местами - это гарантирует, что после всей обработки наибольший элемент диапазона не окажется в начале. Если в диапазоне больше двух элементов, вычисляется треть его длины t, и рекурсивно обрабатываются три перекрывающихся поддиапазона: первые две трети [lo, hi−t], последние две трети [lo+t, hi], и снова первые две трети [lo, hi−t]. Такое тройное перекрывающееся применение гарантирует корректность (это доказуемо, хотя и не очевидно с первого взгляда), но приводит к сложности порядка O(n^log(3)/log(1.5)) ≈ O(n^2.71) - гораздо хуже, чем даже пузырьковая сортировка.

Как это работает

Проследим полный вызов на массиве [4, 1, 3, 2] (n = 4). Верхний вызов rec(0,3) сравнивает 4 и 2, меняет их местами - [2, 1, 3, 4]. Затем t = floor(4/3) = 1, и следуют три вложенных вызова: rec(0,2), rec(1,3), rec(0,2). Первый находит и исправляет пару (2, 1) внутри себя, давая [1, 2, 3, 4]; второй и третий не находят больше нарушений порядка. Итог: массив отсортирован всего за 2 обмена, но ценой 13 рекурсивных вызовов - по одному сравнению на вызов.

Каждый вызов rec делает ровно одно сравнение, поэтому число сравнений равно числу вызовов. Оно растёт стремительно: для n = 9 требуется 121 вызов, для n = 16 - 1093, для n = 27 - 3280 (проверено прямым подсчётом). Для сравнения, пузырьковая сортировка на n = 27 делает не более 27*26/2 = 351 сравнений в худшем случае - Стуз-сортировка тратит на порядок больше работы уже на небольших массивах.

Откуда берётся показатель степени 2.71? Рекуррентное соотношение T(n) = 3T(2n/3) + O(1) по основной теореме о рекуррентных соотношениях (случай, где a = 3 вызовов на подзадачу размера n/b с b = 1.5) даёт T(n) = O(n^(log₃/log₁.₅)). Численно log(3) ≈ 1.0986, log(1.5) ≈ 0.4055, их отношение - ≈ 2.7095, отсюда и заявленная сложность O(n^2.7095).

Ключевая деталь - перекрытие. Если бы диапазон делился на непересекающиеся трети (как в тернарной версии сортировки слиянием), рекуррентное соотношение было бы T(n) = 3T(n/3) + O(n) с логарифмической сложностью O(n log n). Именно перекрытие в две трети вместо непересекающейся трети превращает эффективный тернарный алгоритм в один из худших известных алгоритмов сортировки со стабильно правильным результатом.

Корректность при этом не случайна - её можно доказать индукцией по длине диапазона. Первый вызов гарантирует, что наибольший элемент диапазона не окажется среди первых двух третей после обработки второго вызова (он "прячется" среди последней трети или дальше). Третий вызов затем сортирует первые две трети снова, подтягивая в них всё, что должно там оказаться, включая элементы, "принесённые" вторым вызовом.

Стуз-сортировка часто упоминается как учебное упражнение на вывод и решение рекуррентных соотношений методом основной теоремы - в частности, в книге Udi Manber, «Introduction to Algorithms: A Creative Approach» (1989), где подобные алгоритмы используются, чтобы показать, что интуитивно «похожий на быстрый» рекурсивный алгоритм может оказаться катастрофически медленным при неправильной структуре подзадач.

При этом глубина рекурсии остаётся логарифмической: каждый уровень уменьшает размер диапазона в 1.5 раза (2n/3), поэтому глубина - O(log₁.₅ n), а не O(n), как можно было бы ожидать от алгоритма с такой плохой временной сложностью. Именно поэтому пространственная сложность Стуз-сортировки - всего O(log n), несмотря на почти кубическое время работы.

Нюансы выбора

Никогда для реальной сортировки данных - даже сортировка вставками (O(n²)) или пузырьковая сортировка выигрывают у Стуз-сортировки (O(n^2.71)) на любом n больше нескольких элементов.

При обучении выводу рекуррентных соотношений - Стуз-сортировка даёт наглядный пример перехода от T(n) = aT(n/b) + O(1) к основной теореме, с результатом, который не является ни O(n log n), ни O(n²), ни O(n), а честной дробной степенью.

При сравнении с сортировкой слиянием - contrast полезен именно потому, что оба алгоритма рекурсивно делят диапазон на трети, но merge sort делает это без перекрытия и с явным шагом слияния за O(n), а Стуз-сортировка - с перекрытием и без слияния вовсе.

При обсуждении «ложной интуиции» о рекурсии - студенты часто предполагают, что любое рекурсивное деление диапазона на части даёт O(n log n); Стуз-сортировка - контрпример, показывающий, что решает именно структура подзадач (перекрывающиеся или нет), а не сам факт рекурсии.

Примеры в коде

Udi Manber, «Introduction to Algorithms: A Creative Approach» (Addison-Wesley, 1989) - учебник, где подобные намеренно неэффективные рекурсивные алгоритмы используются как упражнения на анализ рекуррентных соотношений.

Rosetta Code и аналогичные сайты-каталоги алгоритмов реализуют Стуз-сортировку на десятках языков программирования как демонстрацию курьёзной, но корректной рекурсии, а не как практический инструмент.

Списки «худших алгоритмов сортировки» в сообществе программистов неизменно ставят Стуз-сортировку рядом с Бого- и Слоу-сортировкой (Slowsort) как пример того, насколько плохой может быть асимптотика при внешне разумном коде.

Курсы по алгоритмическому анализу (университетские и онлайн) используют вывод показателя log(3)/log(1.5) ≈ 2.71 как готовую задачу применения основной теоремы для рекуррентных соотношений с нецелой степенью в основании логарифма.

Когда применять

• Никогда в реальных задачах - как и Бого-сортировка, Стуз-сортировка существует исключительно как учебный и шуточный пример.
• В обучении рекурсии и анализу сложности - хороший пример того, как перекрывающиеся подзадачи (в отличие от непересекающихся, как в сортировке слиянием) резко ухудшают асимптотику.

Примеры из практики

• Курсы по анализу алгоритмов нередко используют Стуз-сортировку как задачу на вывод рекуррентного соотношения T(n) = 3T(2n/3) + O(1) и его решение методом основной теоремы.
• Списки «алгоритмов-приколов» в сообществе программистов регулярно упоминают Стуз-сортировку рядом с Бого-сортировкой как пример нарочито плохого дизайна.