Smoothsort

Проблема

Heap sort гарантирует O(n log n) в любом случае, но не умеет использовать уже имеющийся порядок в данных - на почти отсортированном массиве он всё равно тратит полное время построения и разбора кучи. Нужен вариант heap sort, который адаптируется к порядку во входных данных, приближаясь к O(n) на почти отсортированных массивах, но сохраняет и гарантию O(n log n), и постоянную память heap sort.

Решение

Вместо одной бинарной кучи на весь массив смузсорт строит последовательность куч Леонардо - специальных бинарных деревьев с размерами по числам Леонардо (аналог чисел Фибоначчи: L(k) = L(k-1) + L(k-2) + 1). Массив постепенно превращается в лес таких куч слева направо (фаза «просеивания вверх»), а затем максимумы куч поочерёдно извлекаются справа налево, как в обычном heap sort. Ключевое отличие: если входные данные уже частично упорядочены, деревья строятся с меньшим числом операций восстановления кучи - отсюда адаптивность и почти линейное время на «гладких» данных.

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

Каждое дерево в лесу смузсорта - это не обычное сбалансированное бинарное дерево, а куча Леонардо порядка k: у неё есть корень и два поддерева - порядка k-1 и k-2 (а не k-1 и k-1, как у кучи из heap sort). Из-за этого размер дерева растёт не как степень двойки, а по формуле L(k) = L(k-1) + L(k-2) + 1, где L(0) = L(1) = 1. Получается последовательность 1, 1, 3, 5, 9, 15, 25, 41... - похожая на числа Фибоначчи, но с добавлением корня на каждом шаге.

В коде leonardo(k) вычисляется лениво и с мемоизацией через массив LEO: он растёт по мере того, как trinkle/siftDown запрашивают всё большие порядки, вместо того чтобы пересчитывать всю последовательность заранее. Для order дерева ровно L(order) - 1 элементов лежат ниже корня, поровну (с точностью до -1) поделённые между левым поддеревом порядка order-1 и правым порядка order-2.

Массив orders - это, по сути, «цифры» числа n, записанного в системе счисления по числам Леонардо: похоже на теорему Цекендорфа для Фибоначчи, где любое число раскладывается в сумму различных чисел Леонардо. Цикл построения (строки 58-68) поддерживает этот инвариант - если два последних дерева стека имеют соседние порядки (k и k-1), они «сливаются» в одно дерево порядка k+1 (строки 59-61), что напоминает перенос разряда при сложении в этой системе счисления. Именно из-за этого инварианта лес никогда не превышает O(log n) деревьев.

Функция trinkle (строки 28-56) - это расширенная версия просеивания вверх: новый элемент всегда попадает в лес как одноузловое дерево справа, и его нужно поднять не только внутри своего дерева, но, возможно, и через границу с соседним деревом. Для этого на каждом шаге сравниваются три кандидата - оба потомка текущего узла (если order > 1) и «пасынок» (`stepson`) - корень предыдущего, меньшего по порядку дерева в лесу, с которым текущий элемент мог бы поменяться местами при постройке.

Если побеждает «пасынок», элемент перепрыгивает в соседнее дерево слева (строки 45-49, r = stepson; i--), и цикл while (true) продолжается уже там - это единственный момент, где просеивание выходит за пределы одного дерева. Если побеждает один из детей, вызывается обычный siftDown (строки 51-53), который восстанавливает свойство кучи уже строго внутри дерева, спускаясь по нему аналогично heap sort, но со смещениями через leonardo(order - 2) вместо 2*i + 1.

Фаза извлечения (строки 70-82) идёт справа налево: последнее дерево леса содержит текущий максимум в своём корне (инвариант леса гарантирует, что корни деревьев слева направо не убывают). Если у извлечённого дерева order > 1, оно распадается на два дочерних дерева порядков order-1 и order-2 (строки 76-79), и оба новых открытых корня повторно проходят trinkle (строки 78-79) - удаление родителя могло нарушить инвариант упорядоченности корней леса.

Худший случай остаётся O(n log n): в лесу до O(log n) деревьев, и trinkle в худшем случае проходит через все их корни при каждой из n вставок/извлечений - для n = 1 000 000 это те же порядка 20 миллионов операций, что и у обычного heap sort. Но на уже отсортированном массиве ни один вызов siftDown/trinkle не находит нарушения (условия if (bigger === root) break и if (winner === r) return срабатывают сразу) - отсюда линейное O(n) в лучшем случае, недостижимое для heap sort.

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

Real-time и embedded системы с жёсткой памятью - когда одновременно нужны гарантия O(n log n), O(1) память и возможность прерваться в любой момент с валидным частичным порядком: ни quicksort (нет гарантии худшего случая), ни Timsort (O(n) память) не закрывают все три требования сразу.

Почти отсортированные потоковые данные без бюджета на лишнюю память - там, где естественным выбором стал бы Timsort, но памяти на буфер слияния прогонов нет.

Не стоит использовать на маленьких массивах (n < 50) - издержки построения леса куч Леонардо и обилие вложенных функций перевешивают выигрыш; insertion sort проще и быстрее на таких размерах.

Не выбирать смузсорт, если не нужны одновременно и гарантия худшего случая, и адаптивность - если достаточно средней скорости, quicksort/introsort быстрее на практике за счёт лучшей локальности кэша.

Хороший выбор для учебных и исследовательских задач о структурах данных - демонстрирует нетривиальное применение чисел Леонардо и леса деревьев как альтернативу единственной куче heap sort.

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

EWD796 - оригинальная рукопись Дейкстры 1981 года «Smoothsort, an alphabetical variant of heapsort», доступна в архиве E.W. Dijkstra Archive Техасского университета в Остине.

Кит Шварц (Keith Schwarz) написал один из самых цитируемых учебных разборов реализации смузсорта на своём личном сайте - оригинальное описание Дейкстры многие практики называют труднопонимаемым без такого разбора.

Встречается в академических курсах по структурам данных (например, Stanford CS166 и аналогичные курсы) как пример нетривиальной кучи, но почти не используется в промышленных стандартных библиотеках (V8, CPython, glibc qsort) - сложность поддержки не окупается небольшим выигрышем над Timsort/introsort.

Иногда упоминается в статьях об алгоритмах сортировки с гарантией прерывания (anytime sorting algorithms) рядом с patience sort - как пример алгоритма, применимого там, где процесс может быть остановлен на полуслове с валидным частично упорядоченным результатом.

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

• Когда данные часто почти отсортированы и важна гарантия O(n log n) без дополнительной памяти (в отличие от Timsort, который использует O(n)).
• В системах с жёсткими ограничениями по памяти, где heap sort уже используется, но хочется адаптивности.

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

• Разработан Эдсгером Дейкстрой в 1981 году как демонстрация того, что можно получить адаптивность heap sort без потери гарантий и памяти - важный академический результат в теории сортировок.
• Встречается в исследовательских реализациях embedded и real-time систем, где важна и гарантия худшего случая, и постоянная память, и возможность прерывания на полуслове.