Quick, по пунктам — для каждого алгоритма: сложность, стабильность, память, поведение на «хороших»/«плохих» входах и практическая рекомендация.
1) QuickSort
- Сложность: средняя и лучшая $\mathcal{O}(n\log n)$, худшая $\mathcal{O}(n^2)$ (при плохом выборе опорного элемента).
- Стабильность: не стабильный (можно сделать стабильным с дополнительной памятью).
- Память: in‑place; стек рекурсии в среднем $\mathcal{O}(\log n)$, в худшем $\mathcal{O}(n)$ (можно уменьшить хвостовой рекурсией/рандомизацией).
- Поведение: очень быстрый на случайных и «хорошо разбивающихся» данных; плох на уже отсортированных/почти отсортированных данных при выборе плохого опорного (решается рандомизацией или median‑of‑three); плохо работает при большом количестве равных ключей без 3‑way partition (с 3‑way — эффективно при множестве дубликатов, иногда близко к $\mathcal{O}(n)$).
- Практика: хороший выбор для общего in‑memory сортирования, когда важна скорость и память ограничена; применять с рандомизацией/median‑of‑three и 3‑way при дубликатах.
2) MergeSort
- Сложность: всегда $\mathcal{O}(n\log n)$ (лучшее/среднее/худшее).
- Стабильность: стабильный (при реализации для массивов с дополнительным буфером).
- Память: требует дополнительного буфера $\mathcal{O}(n)$ для массивов (для связных списков можно реализовать стабильно с $\mathcal{O}(1)$ доп. памятью).
- Поведение: предсказуемо и устойчиво — не подвержен «адверсариальным» входам; хорош для внешней/внутренней сортировки крупной последовательности, легко параллелится; константы могут быть хуже QuickSort из‑за копирования/аллокаций.
- Практика: выбирать когда нужна стабильность, детерминированная временная гарантия, параллелизация или внешняя сортировка (диск), либо при сортировке связных списков.
3) HeapSort
- Сложность: всегда $\mathcal{O}(n\log n)$.
- Стабильность: не стабильный.
- Память: in‑place, дополнительная память $\mathcal{O}(1)$.
- Поведение: гарантированное поведение даже на худших входах, но константы и локальность памяти хуже (много случайных обращений к куче) — обычно медленнее QuickSort на практике.
- Практика: выбирать когда требуется жёсткая гарантия худшего времени и малая доп. память (встраиваемые/реального времени системы), или когда нельзя допускать квадратичную деградацию.
4) IntroSort (Introspective Sort)
- Сложность: средняя $\mathcal{O}(n\log n)$, худшая гарантировано $\mathcal{O}(n\log n)$ (переходит на HeapSort при глубине рекурсии > $c\log n$).
- Стабильность: не стабильный (обычно).
- Память: in‑place; стек $\mathcal{O}(\log n)$.
- Поведение: сочетает практическую скорость QuickSort и гарантии HeapSort — очень надёжен против «плохих» входов; часто дополняется переходом на вставками для маленьких подмассивов.
- Практика: стандартный выбор для библиотечных реализаций (например, std::sort) — лучший компромисс для общего назначения.
Короткие рекомендации:
- Нужна максимальная практическая скорость и экономия памяти → QuickSort/IntroSort (предпочтительно IntroSort в библиотеках).
- Нужна стабильность или внешняя сортировка/хорошая параллелизация → MergeSort.
- Нужна in‑place сортировка с жёсткой гарантией худшего времени и минимум памяти → HeapSort.
- Малые массивы → InsertionSort (или гибрид: Quick/Intro + insertion для маленьких сегментов).
(при всех выборах учитывать: наличие многих равных ключей, требование стабильности, ограничения памяти и возможность параллелизации).