Случаи, сложность
- Случайное (среднее) поведение: при случайном выборе опорного элемента или при рандомизации ожидаемое время работы $O(n\log n)$ и число сравнений примерно $2n\ln n$ (или ≈$1.386n{\log }_{2}n$). Ожидаемая дополнительная память (рекурс. стек) — $O(\log n)$ в среднем.
- Худший случай: при постоянно неудачном выборе опоры (например, уже отсортированный ввод и выбор первого/последнего элемента) рекурсии вырождаются и время $O(n^2)$. Память стека может достигать $O(n)$.
Как уменьшить риск худшего случая
- Рандомизация: выбирать опору случайно → вероятность худшего случая экспоненциально мала.
- Медиана из выборок (median-of-3, median-of-5 или выбор по сэмплу) — улучшает устойчивость на почти-отсортированном вводе.
- Интроспекция (Introsort): при достижении глубины рекурсии ≈ $c\log n$ переключаться на Heapsort, даёт гарантированный худший случай $O(n\log n)$.
Модификации для стабильности
- Стандартный in-place Quicksort не стабилен (отношение равных ключей портится). Возможные подходы:
- Out-of-place стабильный partition: при каждой стадии копировать элементы в три буфера (меньше / равно / больше), сохраняя порядок, затем объединять. Время $O(n\log n)$, доп. память $O(n)$.
- Индексы/ключи: сортировать пары (ключ, исходный индекс) с сравнением по ключу, затем по индексу — стабильность достигается, но увеличивается объём данных.
- Сложные in-place стабильные partition-алгоритмы (ротации блоков) существуют, но они сложны и обычно медленнее (приводят к константным накладным).
- Практическая рекомендация: если нужна стабильность — использовать Mergesort или Timsort (стабильные и быстрые на реальных данных) вместо усложнённого стабильного Quicksort.
Многопоточность (параллелизация)
- Лёгкий способ: рекурсивно порождать задачи для двух подмассивов после partition; выполнять одну часть в текущем потоке, другую — в новом/пуле. Условие спавна: размер подпоследовательности > порог $T$ (например, несколько тысяч элементов) и ограничение числа потоков.
- Параллельный partition: делить массив на блоки, каждый поток подсчитывает и копирует подходящие элементы в локальные буферы, затем выполняется сборка — снижает сериализацию при partition, но требует памяти/синхронизации.
- Использовать пул задач с work-stealing (Cilk, TBB): балансировка нагрузки автоматическая.
- Практические меры: ограничить глубину параллелизма, использовать tail-call оптимизацию/итеративный цикл для одной ветви, переключаться на последовательную сортировку для мелких подзадач.
- Производительность: параллельный Quicksort даёт хорошую масштабируемость при больших массивах и хорошей локальности; для гарантированной параллельной сложности и стабильности часто предпочитают параллельный Mergesort.
Когда выбирать другие алгоритмы
- Нужна стабильность и $O(n\log n)$ в худшем случае → Mergesort или Timsort (Timsort особенно хорош для частично отсортированных данных).
- Ограниченная память и нужна гарантия худшего случая → Heapsort (in-place, худший $O(n\log n)$, нестабилен).
- Много равных ключей → 3-way Quicksort (Dutch National Flag) или адаптивные алгоритмы.
- Малые массивы (обычно $n\lesssim 32$) → Insertion sort (лучше константы).
- Целочисленные ключи в ограниченном диапазоне → Counting sort / Radix sort (линейная сложность $O(n+k)$ или $O(n\cdot \text{digits})$).
- Внешняя сортировка (данные не помещаются в ОЗУ) → внешние варианты merge-sort.
Краткие практические рекомендации
- Общая библиотечная сортировка: использовать оптимизированный Introsort/Quicksort с медианой и доп. переключением на Heapsort + insertion sort для маленьких блоков.
- Если важна стабильность или адаптивность к уже частично отсортированным данным — выбирать Mergesort/Timsort.
- Для параллельной сортировки — реализовывать параллельный Quicksort с порогом спавна и пулом задач или параллельный Mergesort при требовании стабильности/простоты слияния.
(Все асимптотики выше записаны в традиционной нотации: например, среднее время Quicksort $O(n\log n)$, худшее $O(n^2)$.)