Introsort

Проблема

Быстрая сортировка в среднем быстрее всех практических алгоритмов, но на неудачных входных данных (например, уже отсортированный массив с наивным выбором опорного элемента) её рекурсия деградирует до O(n²) и может исчерпать стек вызовов. Библиотечная функция сортировки не может позволить себе такой риск на произвольных пользовательских данных - нужна гарантия наихудшего случая без потери средней производительности quicksort.

Решение

Интроспективная сортировка запускает обычный quicksort, но отслеживает глубину рекурсии. Если глубина превышает порог 2·log₂(n), алгоритм «сдаётся» и досортировывает текущий подмассив пирамидальной сортировкой - у неё гарантированный O(n log n) в худшем случае. На маленьких подмассивах (обычно меньше ~16 элементов) применяется сортировка вставками, так как на таком размере она быстрее из-за низких констант. Так интроспективная сортировка получает среднюю скорость quicksort, гарантию heap sort и эффективность insertion sort на «хвостах».

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

Для случайного массива из 1000 элементов порог глубины maxDepth = 2 * floor(log₂1000) = 18. При прогоне на реальных случайных данных фаза heap sort не запускается ни разу (0 переключений), а insertionSortRange вызывается 115 раз - на всех подмассивах, ставших меньше 16 элементов. Это подтверждает заявление из «Решения»: fallback действительно случается редко, а не «иногда» в абстрактном смысле.

На враждебном входе - уже отсортированном массиве из 1000 элементов, худшем случае для quicksort с опорным a[high] - картина меняется ровно один раз: рекурсия по всё уменьшающимся подмассивам достигает порога depthLimit = 0 на восемнадцатом уровне вложенности, и heap sort запускается ровно 1 раз на оставшемся диапазоне, спасая алгоритм от квадратичного срыва. При этом insertionSortRange всё равно вызывается 18 раз - на маленьких хвостах, отсечённых партиционированием до momента переключения.

На меньшем сортированном массиве из 50 элементов та же картина воспроизводится в миниатюре: maxDepth = 2 * floor(log₂50) = 10, партиционирование доходит ровно до этого предела, heapSortRange вызывается 1 раз, а insertionSortRange - 10 раз. Итоговый массив в обоих случаях (n=50 и n=1000) корректно отсортирован - переключение происходит незаметно для результата, только для затраченной работы.

Порог size < 16 для перехода на insertion sort - не круглое число «для красоты», а эмпирический компромисс: на таком размере накладные расходы рекурсивного вызова и партиционирования quicksort перевешивают квадратичную асимптотику insertion sort, у которой на маленьком n константа мала, а данные почти всегда помещаются в кэш L1. Разные библиотеки используют разные пороги для одной и той же идеи: libstdc++ - 16, реализации MSVC STL исторически используют 32.

Интроспективную сортировку изобрёл Дэвид Р. Массер (David R. Musser) и описал в статье 1997 года «Introspective Sorting and Selection Algorithms» (Software - Practice and Experience). Название «introspective» («самоанализирующая») отражает именно то, что алгоритм следит за собственным поведением (глубиной рекурсии) и меняет стратегию на основе этого наблюдения, а не заранее фиксированного плана.

Почему порог именно 2·log₂(n), а не, скажем, log₂(n) или 3·log₂(n)? Для случайного выбора опорного элемента ожидаемая глубина рекурсии сбалансированного quicksort составляет около 1.39·log₂(n) (тот же результат, что и для средней высоты случайного бинарного дерева поиска). Порог 2·log₂(n) даёт около 44% запаса над этим типичным значением - достаточно, чтобы не переключаться на нормальных данных, но достаточно жёстко, чтобы поймать деградацию раньше, чем она успеет стоить O(n²) работы.

Итог: introsort не меняет асимптотику ни одного из трёх алгоритмов по отдельности - она меняет то, какой именно алгоритм отвечает за каждый конкретный диапазон данных, основываясь на измеримом сигнале (размер и глубина), а не на предположении о структуре входа. Это и есть его практическая сила: гарантия худшего случая, купленная почти без потерь в среднем случае.

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

Как реализация `std::sort` или её эквивалента в новой библиотеке - когда нужна гарантия худшего случая, сравнимая со скоростью quicksort на типичных данных, и неустойчивость сортировки допустима.

Против чистого quicksort - если входные данные могут быть подобраны злонамеренно (например, сервис принимает пользовательские массивы для сортировки), introsort устраняет риск атаки на алгоритм через специально сконструированный худший случай.

Против heap sort как основного алгоритма - если типичные данные преобладают над враждебными, introsort почти всегда быстрее на практике за счёт того, что чистый heap sort запускается только в крайне редких случаях.

Не выбирать, если нужна устойчивость сортировки - ни один из трёх компонентов (quicksort, heap sort, insertion sort в этой реализации без учёта равенства) не гарантирует сохранение порядка равных элементов; для этого нужен Timsort или merge sort.

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

David R. Musser, «Introspective Sorting and Selection Algorithms» (Software - Practice and Experience, 1997) - оригинальная статья, вводящая introsort и доказывающая его гарантию O(n log n) в худшем случае.

libstdc++ (реализация GCC для C++ STL) - использует порог 16 для перехода на insertion sort и явно документирует лимит глубины 2 * log2(n) в исходном коде stl_algo.h.

Атаки на алгоритмическую сложность (algorithmic complexity attacks) - класс уязвимостей, при которых злоумышленник подбирает вход, вызывающий худший случай алгоритма; introsort - стандартная защита от такой атаки специально для сортировки на стороне сервера.

Go, начиная с версии 1.19 - встроенная функция sort.Sort использует паттерн pattern-defeating quicksort (pdqsort), развивающий ту же идею introsort с дополнительными эвристиками против типичных враждебных паттернов.

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

• Как универсальная сортировка общего назначения в библиотеке, где нужна и высокая средняя скорость, и гарантия худшего случая.
• Когда неустойчивость сортировки не критична, а важна именно производительность на произвольных данных.

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

• C++ STL - std::sort в большинстве реализаций (libstdc++, libc++) - это интроспективная сортировка.
• .NET / C# - Array.Sort использует гибрид quicksort/heapsort/insertion sort, концептуально идентичный introsort.