Introsort

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

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

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

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

Литература

• Мюссер, Дэвид (1997). «Introspective Sorting and Selection Algorithms». Software: Practice and Experience (Wiley) 27 (8): 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.