STL Сортировка против медианы медиан

Question

std :: sort () использует алгоритм Introsort , который переключается между быстрой сортировкой и сортировкой кучи в зависимости от текущего коэффициента разделения.

Есть ли практический недостаток для реализации Median-of-Медиана Быстрая сортировка вместо Интросорта?В конце концов, теоретически сложнее смоделировать смесь алгоритмов сортировки и вычислить их наихудшую сложность - хотя я предполагаю, что интросорт будет O (N log N).

Answer 1

См. Оригинальную статью Мюссера о Introsort. По сути, хотя Медиана медиан и Интросорт одинаково асимптотически, Интросорт выполняет менее постоянную работу на элемент и, как правило, быстрее. В документе упоминается, что Median of Medians будет в качестве запасного варианта вместо Heap Sort.

Дэвид Р. Муссер. Алгоритмы интроспективной сортировки и отбора. [Постскриптумная версия]

Answer 2

Из того, что я помню, Quicksort плохо работает с отсортированными или почти отсортированными коллекциями - O (n ^ 2). Посетите страницу Википедии по Introsort - с убедительной статистикой по Introsort vs. Quicksort.