Кратко — принципы, почему бывает большая разница во времени, примеры входных данных и практические критерии выбора.
1) Принципы работы (суть)
- Quicksort: выбирается опорный элемент (pivot), массив делится на две части: элементы pivot, рекурсивно сортируются. Разделение делается «на месте» (partition).
- Merge sort: рекурсивно делит массив пополам, сортирует половины и затем выполняет слияние двух отсортированных массивов в дополнительный буфер.
2) Асимптотики (в KaTeX)
- Quicksort: среднее и ожидаемое время $O(n\log n)$, худший случай $O(n^2)$. Доп. память обычно $O(\log n)$ для стека (in-place partition), в худшем случае $O(n)$ рекурсий.
- Merge sort: всегда $O(n\log n)$ (лучший/средний/худший), доп. память $O(n)$ для слияния (для массивов); для списков можно реализовать с $O(1)$ доп. памяти.
3) Почему один может значительно превосходить другой
- Quicksort быстрее на практике для больших in-memory массивов из‑за лучшей локальности памяти и меньшего числа копирований/аллок. Partition делает много локальных операций, меньше чтений/записей в память, поэтому константы при $O(n\log n)$ меньше.
- Однако при плохом выборе pivot (например, всегда первый элемент) или на уже отсортированных/почти отсортированных входах Quicksort даёт сильно несбалансированные разбиения. Тогда рекуррентное соотношение:
$$T(n)=T(n-1)+O(n)\Rightarrow T(n)=O(n^2)$$ Merge sort при тех же данных остаётся
$$T(n)=2T(n/2)+O(n)\Rightarrow T(n)=O(n\log n).$$
4) Конкретные примеры входных данных
- Случай, где Merge sort значительно лучше Quicksort (наивный pivot):
- вход: уже отсортированный массив или обратный отсортированный массив, pivot = первый/последний элемент. Quicksort превращается в $O(n^2)$, а Merge sort остаётся $O(n\log n)$.
- Случай, где Quicksort быстрее Merge sort:
- большой случайный массив в оперативной памяти; Quicksort (с хорошим pivot — median-of-three или случайным) обычно быстрее из‑за лучшей кэш-локальности и меньших накладных расходов при копировании. На практике Quicksort/Introsort часто быстрее при больших n.
5) Дополнительные факторы (почему и когда выбирать)
- Требуется стабильность (сохранение порядка равных ключей): выбирать Merge sort (он стабильный) или стабильную реализацию Quicksort (сложнее).
- Ограниченная дополнительная память: Quicksort (in-place) выигрывает; Merge sort требует $O(n)$ для массивов.
- Гарантированное время в худшем случае: Merge sort гарантированно $O(n\log n)$; для Quicksort ставят Introsort (Quicksort + переход на Heapsort при глубокой рекурсии) чтобы получить гарантии.
- Внешняя сортировка / списки: Merge sort лучше (хорош для внешней памяти и сортировки связных списков — слияние без доп. памяти).
- Много одинаковых ключей: обычный Quicksort может деградировать, но 3-way partitioning (Dijkstra) решает это; Merge sort спокойно справляется.
- Параллелизация: Merge sort легко параллелизуется (независимые слияния), Quicksort — сложнее из‑за балансировки.
6) Практические рекомендации
- Общая in-memory сортировка: использовать современную реализацию Introsort (Quicksort + Heapsort при плохой глубине) — быстрый и с гарантией.
- Нужна стабильность или работа с внешней памятью/списками: Merge sort / Timsort (Python/Java используют гибриды, учитывающие уже упорядоченные «руны»).
- Очень мало памяти: in-place Quicksort.
- Возможность атак/худших случаев (ввод от пользователя/не доверенные данные): выбирать подход с защитой (randomized pivot или Introsort).
Кратко: Quicksort обычно быстрее на практике благодаря кэш‑локальности и in-place работе, но уязвим к плохому выбору pivot (может стать $O(n^2)$); Merge sort даёт предсказуемое $O(n\log n)$, стабилен и хорош для внешней памяти, но требует доп. памяти. Выбор основывайте на требованиях к памяти, стабильности, гарантированному времени и типу входных данных.