Коротко — эти три алгоритма имеют одинаковый асимптотический класс в среднем ($O(n\log n)$) но сильно отличаются константами, использованием памяти, устойчивостью и чувствительностью к паттернам входа, поэтому на больших данных практические результаты различаются.
По критериям (сравниваю быстрое(Quicksort), слиянием(Mergesort), кучей(Heapsort)):
- Время (асимптотика и практические константы)
- Quicksort: среднее время $O(n\log n)$, худшее $O(n^2)$ (при плохом выборе опорного элемента). На практике самый быстрый из‑за маленьких констант и отличной локальности доступа (частые последовательные проходы по массиву).
- Mergesort: гарантированно $O(n\log n)$ в любом случае. Константы выше, чем у quicksort, но стабильная производительность и предсказуемость.
- Heapsort: гарантированно $O(n\log n)$. Константы обычно самые большие — много сравнений и перестановок, плохая локальность кэша, потому на больших массивах он часто медленнее двух других.
- Память
- Quicksort: обычно in‑place, доп. стековая память $O(\log n)$ в среднем (рекурсия), в худшем $O(n)$ если плохая балансировка (но это снимается случайным выбором/Introsort).
- Mergesort: для массивов требует доп. память $O(n)$ (стабильное слияние); есть варианты bottom‑up и внешние реализации; для связанных списков можно сделать $O(1)$ доп. памяти.
- Heapsort: in‑place, доп. память $O(1)$.
- Устойчивость (stable)
- Quicksort: обычно нестабилен (можно сделать стабильным с доп. памятью, но теряется эффективность).
- Mergesort: стабилен при стандартной реализации.
- Heapsort: нестабилен (стабильная версия требует сложных модификаций и доп. памяти).
- Паттерны входа (чувствительность)
- Отсортированный или почти отсортированный:
- Quicksort: наивная реализация (пивот = первый/последний) может деградировать до $O(n^2)$. С median‑of‑three, случайным пивотом или Introsort — чувствительность снимается. Quicksort+инсершен для коротких отрезков хорошо использует почти отсортенность.
- Mergesort: практически не чувствителен — всегда $O(n\log n)$; для почти отсортированных данных может быть избыточен по работе, но легко комбинируется с распознаванием «ранов» (natural mergesort).
- Heapsort: не чувствителен к порядку, время почти одинаково для любых входов.
- Много одинаковых ключей:
- Quicksort: стандартный двухсторонний partition может сильно деградировать; трёхсторонняя (Dutch national flag) даёт хорошую производительность (часто $O(n)$ на равных ключах).
- Mergesort/Heapsort: справляются корректно и предсказуемо.
- Внешние/потоковые данные:
- Mergesort лучше всего (последовательные чтения/записи, легко масштабируется на диск).
- Quicksort/Heapsort не подходят для внешней сортировки без модификаций.
- Кэш‑поведение и предсказуемость ветвлений
- Quicksort: хорошая локальность (сканирование сегментов), поэтому быстро на реальных машинах; но partition содержит ветвления, которые бывают непредсказуемы.
- Mergesort: регулярный последовательный доступ — хорошая предсказуемость ветвей и кэш‑поведение для больших буферов.
- Heapsort: много произвольных обращений (верх/низ кучи) — плохая локальность и много промахов в кэше, хуже предсказуемость ветвей.
Практические заметки и рекомендации
- Для общего назначения на in‑memory массивах обычно выбирают Quicksort с хорошим пивотом и падением на Heapsort при глубокой рекурсии (Introsort) — это дает скорость Quicksort с гарантиями.
- Для стабильной сортировки или внешней сортировки выбирают Mergesort (или Timsort — гибрид, использующий натуральные раны).
- Если критично ограничение памяти или нужна строгая гарантия по времени — Heapsort.
- Для данных с множеством одинаковых ключей используйте трёхсторонний partition или Mergesort/Timsort.
Коротко: Quicksort — самый быстрый в среднем (лучше кэш), чувствителен к плохим пивотам; Mergesort — стабильный и предсказуемый, требует доп. памяти, идеален для внешней сортировки; Heapsort — in‑place с худшими константами, хорош когда важны память и гарантии.