Введение
Гибридный алгоритм сортировки
Introsort, или интроспективная сортировка, — это гибридный алгоритм сортировки, обеспечивающий высокую среднюю производительность и (асимптотически) оптимальную производительность в худшем случае. Он начинается с быстрой сортировки, переключается на пирамидальную сортировку, когда глубина рекурсии превышает уровень, основанный на (логарифме) количества сортируемых элементов, и переключается на сортировку вставками, когда количество элементов опускается ниже определенного порога. Это сочетает в себе преимущества всех трех алгоритмов, обеспечивая практическую производительность, сопоставимую с быстрой сортировкой на типичных наборах данных, и гарантированное время работы в худшем случае O(n log n) благодаря пирамидальной сортировке. Поскольку все три используемых алгоритма являются сортировками сравнения, Introsort также является сортировкой сравнения. Introsort был изобретен Дэвидом Муссером в 1991 году, где он также представил introselect — гибридный алгоритм выбора, основанный на quickselect (варианте быстрой сортировки), который переключается на алгоритм «медиана медиан», обеспечивая тем самым линейную сложность в худшем случае, что является оптимальным. Оба алгоритма были разработаны с целью предоставления универсальных алгоритмов для Стандартной библиотеки C++, обладающих высокой средней производительностью и оптимальной производительностью в худшем случае, что позволило повысить требования к производительности. Introsort выполняется на месте и является нестабильным алгоритмом.
Анализ
В быстрой сортировке одной из критических операций является выбор опорного элемента: элемента, вокруг которого происходит разделение списка. Самый простой алгоритм выбора опорного элемента – взять первый или последний элемент списка в качестве опорного, что приводит к неэффективной работе при отсортированном или почти отсортированном вводе. Вариант, предложенный Никлаусом Виртом, использует средний элемент, чтобы избежать этих ситуаций, но при этом деградирует до O(n²) для специально подобранных последовательностей. Алгоритм выбора опорного элемента как медианы из трёх берёт медиану первого, среднего и последнего элементов списка; однако, даже несмотря на то, что он хорошо работает для многих реальных входных данных, всё ещё возможно создать "убийцу медианы из трёх" – последовательность, которая вызовет резкое замедление быстрой сортировки, основанной на этой технике выбора опорного элемента. Массер сообщил, что на "убийце медианы из трёх" из 100 000 элементов время работы интросорта было в 200 раз меньше, чем у быстрой сортировки с медианой из трёх. Массер также исследовал влияние на кэш отложенной сортировки небольших диапазонов Седжвика, где небольшие поддиапазоны сортируются в конце одним проходом сортировкой вставками. Он сообщил, что это может удвоить количество промахов кэша, но производительность с использованием двусторонних очередей была значительно лучше, и эту возможность следует сохранить в библиотеках шаблонов, поскольку выигрыш в других случаях от немедленной сортировки был незначительным.
Реализация
Интросортировка или один из её вариантов используется во многих стандартных функциях сортировки библиотек, включая некоторые реализации сортировки в C++. В июне 2000 года реализация нестабильной сортировки в библиотеке стандартных шаблонов SGI C++ (файл stl_algo.h) использовала подход интросортировки Массера с переключением на пирамидальную сортировку при достижении заданной глубины рекурсии (передаваемой как параметр), выбором опорного элемента как медианы из трёх и финальным проходом сортировки вставками по Кнуту для разделов размером менее 16. Библиотека GNU Standard C++ аналогична: использует интросортировку с максимальной глубиной 2 × log2 n, за которой следует сортировка вставками для разделов размером менее 16. LLVM libc++ также использует интросортировку с максимальной глубиной 2 × log2 n, однако пороговое значение размера для сортировки вставками различается для разных типов данных (30, если перестановки тривиальны, и 6 в противном случае). Кроме того, массивы размером до 5 обрабатываются отдельно. Кутенин (2022) предоставляет обзор некоторых изменений, внесённых в LLVM, с акцентом на исправление квадратичной сложности в 2022 году. Библиотека классов Microsoft .NET Framework, начиная с версии 4.5 (2012), использует интросортировку вместо простой быстрой сортировки. Go использует модификацию интросортировки: для срезов из 12 или менее элементов применяется сортировка вставками, а для более крупных срезов – быстрая сортировка с предотвращением дегенеративных случаев и более продвинутый выбор опорного элемента как медианы из трёх медиан. До версии 1.19 использовалась сортировка Шелла для небольших срезов. Java, начиная с версии 14 (2020), использует гибридный алгоритм сортировки, применяющий сортировку слиянием для массивов с высокой степенью упорядоченности (состоящих из небольшого числа отсортированных подмассивов) и интросортировку для сортировки массивов типов int, long, float и double.
Общий
Никлаус Вирт. Алгоритмы и структуры данных. Prentice Hall, Inc., 1985.