Кратко и по делу — сравнение по сложности, преимуществам и ограничениям для работы с большими данными.
1) Внешняя сортировка (обычно внешняя сортировка слиянием)
- Сложность (CPU): обычно $O(N\log N)$.
- Сложность ввода/вывода: критична; число проходов по данным ~ $1+\lceil {\log }_d(R)\rceil$, где $R$ — начальное число отсортированных "прогонов" (runs), $d$ — степень многопутевого слияния (приблизительно число блоков/буферов, умещающихся в памяти). И/O-стоимость примерно пропорциональна количеству проходов: $O(\frac{N}{B}\cdot \text{passes})$ (B — размер блока).
- Преимущества:
- Проектирована для данных, не помещающихся в ОЗУ; оптимальна по I/O при выборе большой степени слияния.
- Стабильна (если реализована как слияние).
- Хорошо масштабируется: многопутевое слияние, параллельные/распределённые реализации.
- Можно улучшать начальные прогоны replacement selection (используя кучу) для удлинения прогонов.
- Ограничения:
- Затраты на диск/сеть доминируют; производительность чувствительна к параметрам блока и объёму памяти.
- Требует организации буферов, менеджмента I/O; сложнее реализовать эффективно на малых размерах.
2) Пирамидальная сортировка (heap sort)
- Сложность: время $O(N\log N)$ в худшем и среднем случае, дополнительная память $O(1)$ (in-place).
- Преимущества:
- Предсказуемая худшая сложность, экономия памяти (in-place).
- Простая реализация для внутренней сортировки в ограниченной памяти.
- Ограничения:
- Плохая локальность доступа (много случайных обращений), что делает её неэффективной при внешних I/O (хорошо только при данных в памяти).
- Не устойчива (не stable).
- Не так хорошо параллелится и кешируется, как quicksort/mergesort.
- Для больших внешних наборов данных требует многочисленных произвольных обращений и потому не подходит.
3) Алгоритмы на основе разделения (divide-and-conquer: quicksort, mergesort, sample sort и т.п.)
- Quicksort:
- Сложность: средняя $O(N\log N)$, худшая $O(N^2)$ (можно избежать рандомизацией или introsort); доп. память $O(\log N)$ (стек), in-place вариант.
- Преимущества: отличная кеш-локальность и константы, очень быстрый на внутренних данных; хорошо параллелится (разделяй и властвуй).
- Ограничения: худший случай, нестабилен (по умолчанию), плохо подходит для внешней сортировки без специальных модификаций.
- Mergesort (внутренний):
- Сложность: $O(N\log N)$ в худшем и среднем; доп. память $O(N)$ или можно делать in-place с усложнением.
- Преимущества: стабильность, предсказуемость, простое распределение задач для параллелизма; естественно адаптируется в внешнюю многопутевую сортировку (внешний mergesort).
- Ограничения: дополнительная память обязана (если не применять сложные in-place методы); при малых буферах — больше I/O, чем оптимальный внешний алгоритм.
Краткое сопоставление по критериям
- При данных, не помещающихся в ОЗУ: предпочтительна внешняя сортировка (внешний mergesort, sample sort, распределённый merge), поскольку оптимальна по I/O. Heap sort и обычный quicksort плохо подходят.
- По использованию памяти: heap sort — $O(1)$ (in-place); quicksort — $O(\log N)$; mergesort — $O(N)$ (внутренний) или с контролируемой памятью во внешнем варианте.
- По стабильности: внешнее слияние и mergesort — стабильны; quicksort/heap sort — обычно нестабильны.
- По параллелизации: divide-and-conquer (quicksort/mergesort) и многопутевое внешнее слияние — хорошо параллелятся; heap sort — хуже.
- По чувствительности к I/O/локальности: mergesort/external merge — оптимизированы для последовательного I/O; quicksort — хорош в памяти; heap sort — плох по локальности.
Вывод: для больших данных, не помещающихся в память, основной выбор — внешняя сортировка (многопутевое слияние или распределённые варианты). Для внутренних ограниченных по памяти задач — пирамидальная сортировка полезна из‑за $O(1)$ памяти, но обычно на практике предпочитают быстрый quicksort (или гибриды) из‑за лучшей кеш‑локальности и констант.