Кратко и по делу.
Почему и когда quicksort деградирует до $O(n^2)$ - Неправильный выбор опорного элемента (pivot). Если на каждом шаге разбиение даёт очень несбалансированные части, например размеры $n-1$ и $0$, то рекуррентное соотношение
$$T(n)=T(n-1)+\Theta (n)$$ даёт $T(n)=\Theta (n^2)$. Это происходит, например, при сортировке уже отсортированных или обратно отсортированных массивов, если всегда брать первый/последний элемент как pivot.
- Много одинаковых ключей + обычная двухсторонняя (двухчастная) схема разбиения (Lomuto/простая Hoare). Тогда каждый раз один из частей может быть почти того же размера, и получается та же квадратичная деградация.
- Атаки на детерминированный выбор pivot (враждебные входы), если алгоритм использует фиксированное правило (например, всегда средний индекс) — можно сконструировать последовательности, приводящие к плохому разбиению.
Практические эвристики и модификации (с обоснованием)
- Рандомизация pivot:
- Выбирать pivot случайно или предварительно перемешать массив (Fisher–Yates). Обоснование: ожидаемая сложность становится $\Theta (n\log n)$ и исчезает зависимость от порядка входа; трудно сконструировать худший случай.
- Median-of-three / Tukey ninther:
- Для каждого вызова брать pivot = медиана $\{A[lo],A[mid],A[hi]\}$ (median-of-three); для больших массивов — медиана трёх медиан (Tukey ninther). Обоснование: уменьшает шанс плохого разбиения на уже- или почти-отсортированных данных с низкой накладной.
- Трёхстороннее разбиение (Dutch National Flag):
- Разбивать на три части: pivot. Особенно эффективно при многих равных ключах — алгоритм работает близко к $\Theta (n)$ при большом числе дубликатов и избегает деградации.
- Использовать Hoare partition или улучшенную реализацию Lomuto:
- Hoare часто делает меньше обменов/сравнений и лучше ведёт себя на практике. (Нужно аккуратно обрабатывать границы при рекурсии.)
- Мелкие подмассивы — insertion sort:
- Для подмасивов размера $\le k$ (типично $k=8\dots 32$, часто $16$) переключаться на insertion sort. Обоснование: константы меньшие на коротких участках, суммарный выигрыш.
- Tail-recursion elimination / рекурсия на меньшей части:
- Всегда рекурсивно обрабатывать меньшую из частей, а для большей — цикл (или рекурсия в конце). Гарантирует глубину стека $\Theta (\log n)$ в среднем и в лучшем случае.
- Introsort (практическая гарантия):
- Запускать quicksort с рандом/median-of-three; если глубина рекурсии превышает $c{\log }_{2}n$ (обычно $c=2$), переключаться на heapsort для оставшейся части. Обоснование: комбинация даёт скорость quicksort на "обычных" данных и гарантированное $\Theta (n\log n)$ в худшем случае.
- Детерминированная гарантия через median-of-medians:
- Можно выбирать точную медиану за $\Theta (n)$ (алгоритм selection), тогда каждый pivot даёт гарантированно сбалансированное разбиение и общее $\Theta (n\log n)$ в худшем случае. Обоснование: строгие гарантии; недостаток — большая константа, поэтому редко используется на практике.
- Защита от враждебных входов:
- Обязательное предварительное перемешивание массива или использование случайного pivot устраняет возможность атакующих входов.
Рекомендуемая практическая конфигурация
- Перемешать массив (или использовать случайный pivot).
- Pivot = median-of-three (или ninther для очень больших массивов).
- Использовать Hoare partition или 3-way partitioning при подозрении на много дубликатов.
- Для подмассивов длины $\le 16$ — insertion sort.
- Реализовать tail-recursion elimination (рекурсия только на меньшей части).
- Ввести introsort: при глубине > $2{\log }_{2}n$ — переход на heapsort.
Эти меры дают: на реальных данных — быструю работу близко к $\Theta (n\log n)$ с малыми константами; в худшем случае — гарантию $\Theta (n\log n)$ (через introsort или median-of-medians).