Кратко: median-of-three снижает шанс плохих разбиений, но не устраняет их полностью — при специально сконструированных входах или при большом числе равных ключей быстрая сортировка всё ещё может деградировать до $O(n^2)$. Ниже — сценарии и практические способы предотвратить деградацию.
Когда возникает $O(n^2)$ - Атакующие / специально сконструированные входы: можно построить последовательности, при которых для каждого шага медиана из (первого, среднего, последнего) будет близка к экстремуму и даст очень неравные разбиения. Для любой детерминированной схемы выбора опоры существует «killer»-вход, приводящий к $O(n^2)$.
- Много равных ключей при стандартной двухпутной (Lomuto) партиции: если опора равна многим элементам, разбиение может уменьшать размер подмассивов лишь на константу, давая квадратичную сложность.
- Плохая реализация партиции (например, неоптимизированный Lomuto) или отсутствие защиты от глубокой рекурсии — усугубляют проблему.
Практические способы предотвращения деградации
- Перемешивание массива (shuffle) перед сортировкой: делает вероятность «хорошего» входа почти единичной, ожидаемая сложность становится $O(n\log n)$.
- Случайный выбор опоры (random pivot) или медиана из случайной выборки: существенно снижает шанс целенаправленного «killer»-входа.
- Трёхпутная партиция (Dutch National Flag) при наличии многих равных ключей: гарантирует, что все равные опоре элементы группируются в средний участок, предотвращая деградацию из-за повторов.
- Introsort (переход на Heapsort при слишком большой глубине рекурсии): даёт гарантированное худшее время $O(n\log n)$ с практической скоростью quicksort.
- Использовать «медиану медиан» (median-of-medians) как опору для жёсткой гарантии баланса — даёт детерминированное худшее $O(n\log n)$, но с большими константами.
- Отдавать предпочтение Hoare-партиции и оптимизациям (tail recursion elimination, переход на insertion sort для мелких подмассивов) — ускоряет практическую работу и уменьшает расходы на рекурсию.
Резюме: median-of-three уменьшает вероятность худшего случая, но не даёт формальной гарантии. В практике обычно достаточно перемешивания/случайного выбора + 3-way партиции; для жёстких гарантий используют introsort или median-of-medians.