Кратко и по существу — сравнение по времени и памяти, практические рекомендации и критерии выбора для стандартной библиотеки.
1) Сравнение (время — типичное/среднее и худшее; память — дополнительная, стабильность, адаптивность)
- Timsort
- время: типичное/среднее $O(n\log n)$, лучший случай (почти отсортированные данные) $O(n)$, худший $O(n\log n)$.
- память (доп.): в реализации обычно до $O(n)$ в худшем случае (в реальности буфер равен длине текущего run, но асимптотически $O(n)$).
- свойства: стабильный, адаптивный (эффективен на частично отсортированных данных), хорошая локальность доступа, более высокий константный фактор по сравнению с быстрым QuickSort в простых случаях, сложнее реализация.
- QuickSort (классический, сравнивая сравнения/обмены)
- время: типичное/среднее $O(n\log n)$, худший $O(n^2)$ (нападение на плохой выбор опорного элемента).
- память: дополнительная $O(\log n)$ (стек рекурсии) в среднем, в худшем $O(n)$ при неудачной рекурсии (можно уменьшить итеративной реализацией).
- свойства: нестабильный (обычно), очень хорошие константы и кэш-поведение, простой in‑place алгоритм. Без защиты — риск худшего случая; с рандомизацией/пивотом по медиане трёх или с Introsort — устраняется худший-case проблема.
- MergeSort
- время: типичное и худшее $O(n\log n)$ (детерминированно).
- память: дополнительная $O(n)$ для классической реализации; существуют in‑place варианты, но они сложнее и медленнее на практике.
- свойства: стабильный (при стандартной реализации), хорош для внешней сортировки и параллелизации, предсказуемые характеристики, хуже кэш‑локальности и больше дополнительных перемещений по сравнению с QuickSort.
2) Когда предпочесть каждый алгоритм (практически)
- Timsort — когда важна стабильность и адаптивность: сортировка объектов/записей в стандартной библиотеке для пользовательских типов, данные часто частично отсортированы (логичные последовательности, записи по времени). Примеры: Python list.sort(), Java Arrays.sort(Object[]).
- QuickSort (быстрая in‑place реализация) — когда нужна максимальная скорость и низкое потребление памяти для примитивных типов, где нестабильность допустима; хорош для небольших и случайных наборов данных. На продакшне обычно используют защищённые варианты (рандомизация, медиана‑трёх) или Introsort.
- MergeSort — когда нужна стабильность + гарантированное $O(n\log n)$ время и/или удобство параллелизации и внешняя сортировка (крупные данные на диске). Также хорош для реализации stable sort для стандартной библиотеки, если допускается дополнительная память.
3) Критерии выбора для стандартной библиотеки языка
- требование стабильности: если API обещает стабильность — выбрать адаптивный стабильный алгоритм (Timsort или стабильный MergeSort).
- гарантия худшего случая: если нужно строгое ограничение времени — выбрать алгоритм с гарантией $O(n\log n)$ (MergeSort) или использовать Introsort (QuickSort с переходом на HeapSort) для in‑place и гарантии.
- потребление памяти: если ограничена доп. память — предпочесть in‑place алгоритм (QuickSort/Introsort или Dual‑Pivot QuickSort), если память доступна — Merge/Timsort для стабильности/адаптивности.
- тип данных: для целых чисел/ключей — рассмотреть некoмпаративные алгоритмы (radix sort) при подходящей модели данных; для объектов — стабильность и копирование важны.
- производительность на реальных данных: учитывать кэш‑локальность и константы; QuickSort/Introsort часто быстрее на случайных данных.
- параллелизация: MergeSort и его параллельные варианты легче распараллеливаются; для многопоточности учесть это.
- сложность реализации и поддерживаемость: Timsort сложнее; Introsort и MergeSort — реализуемы и проверены.
- детерминированность/сопротивление атакам: если важна защита от специально подобранных входов — избегать чистого QuickSort без защиты (использовать Introsort или рандомизацию).
4) Практическое предложение для стандартной библиотеки (рекомендации)
- Для общего "unstable" sort (быстрая сортировка примитивов): Introsort (QuickSort + HeapSort fallback) или иная хорошо проверенная быстpая in‑place реализация (низкая память, $O(n\log n)$ худший случай, быстрые константы).
- Для stable sort (объекты, гарантии порядка равных элементов): Timsort (адаптивный, быстрый на почти отсортированных данных) или стабильный MergeSort; Timsort — предпочтителен, если ожидается много частично отсортированных входов.
- Для больших/внешних задач или параллельного выполнения: использовать сортировки на основе Merge (внешняя/параллельная MergeSort) или специализированные parallel-sample-sort.
- Для целочисленных ключей при больших объёмах — radix/побитовые методы, если допустима нестандартная сравнительная модель.
Вывод (коротко):
- Если нужна стабильность и адаптивность: выбрать Timsort.
- Если нужна максимальная скорость in‑place и низкая память: Introsort/QuickSort с защитой от худшего случая.
- Если нужна простая гарантия $O(n\log n)$ и лёгкая параллелизация: MergeSort.