Introsort

Introsort или интроспективная сортировка — алгоритм сортировки, предложенный Дэвидом Мюссером в 1997 году. Он использует быструю сортировку и переключается на пирамидальную сортировку, когда глубина рекурсии превысит некоторый заранее установленный уровень (например, логарифм от числа сортируемых элементов). Этот подход сочетает в себе достоинства обоих методов с худшим случаем O(n log n) и быстродействием, сравнимым с быстрой сортировкой. Так как оба алгоритма используют сравнения, этот алгоритм также принадлежит классу сортировок на основе сравнений.

В быстрой сортировке одна из критичных операций — выбор опоры (элемент, относительно которого разбивается массив). Простейший алгоритм выбора основы — взятие первого или последнего элемента массива за опору чревато плохим поведением на отсортированных или почти отсортированных данных. Никлаус Вирт предложил использовать серединный элемент для предотвращения этого случая, деградирующего до O(n²) при неудачных входных данных. Алгоритм выбора опоры «медиана трёх» выбирает опорой средний из первого, среднего и последнего элементов массива. Однако, несмотря на то, что он работает хорошо на большинстве входных данных, все же возможно найти такие входные данные, которые сильно замедлят этот алгоритм сортировки. Такие данные потенциально могут использоваться злоумышленниками. Например, злоумышленники могут посылать такой массив Веб-серверу, добиваясь отказа в обслуживании.

Мюссер выяснил, что на худшем наборе данных для алгоритма быстрой сортировки «медиана из трёх» (рассматривался массив из 100 тысяч элементов) introsort работает примерно в 200 раз быстрее. Он также оценил эффект от кеша в случае сортировки Роберта Седжвика, когда небольшие диапазоны сортируются в конце одиночным проходом сортировки вставками. Он выяснил, что такой подход может удвоить количество промахов кеша, но его производительность при использовании двухсторонней очереди значительно лучше, и его следует оставить для библиотек шаблонов, отчасти потому, что выигрыш в других случаях не велик.

В реализации Стандартной библиотеки шаблонов C++ от SGI (stl_algo.h) для неустойчивой сортировки используется подход Мюссера с контролем глубины рекурсии, для переключения на алгоритм пирамидальной сортировки, выбор неподвижного элемента как медианы из трёх и в конце применяется алгоритм сортировки вставками Кнута для последовательностей, содержащих менее чем 16 элементов.

Литература

• Мюссер, Дэвид. Introspective Sorting and Selection Algorithms (англ.) // Software: Practice and Experience. — Wiley, 1997. — Vol. 27, no. 8. — P. 983—993. — doi:10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#.

• Никлаус Вирт. «Алгоритмы и структуры данных». Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1.

Ссылки

• «Введение в introsort» Доклад, созданный Ральфом Унденом в рамках студенческого исследования. Содержит реализацию на Java.