Средняя и худшая сложность
- Средняя: для quicksort с выбором опорного элемента как median-of-three ожидаемая сложность остается $\Theta (n\log n)$. Для классического (рандомизированного) quicksort ожидаемое число сравнений оценивается примерно как $\sim 2n\ln n$ (то есть $\Theta (n\log n)$); median-of-three уменьшает константу (улучшает качество разбиения), поэтому ожидаемое число сравнений остаётся пропорционально $n\ln n$ с меньшим множителем: примерно $\sim cn\ln n$ при $c<2$ (зависит от модели и точного анализа).
- Худшая: медиана из трёх не даёт теоретической гарантии против квадратичного поведения, худший случай по времени остаётся $\Theta (n^2)$ — существуют специально сконструированные (так называемые «killer») входы, при которых median-of-three постоянно даёт сильно несбалансированные разбиения.
Влияние «killer» (специально подобранных) входных данных
- Такие входы подбираются так, чтобы три контролируемых элемента (обычно первый, средний, последний) давали плохую медиану на каждом шаге, что приводит к рекурсивно очень неравным частям и квадратичному времени.
- Частый практический «плохой» случай — большое число равных ключей или специально упорядоченные/структурированные последовательности; median-of-three хорошо защищает от уже полностью отсортированных массивов (выбирает средний элемент), но может быть побеждена искусственными конструкциями.
Стратегии для гарантии и стабильной производительности
- Перемешивание (shuffle) входа перед сортировкой: делает поведение против входа случайным, даёт ожидаемое время $O(n\log n)$ независимо от исходного порядка.
- Introsort: использовать quicksort с выбором median-of-three, но при достижении глубины рекурсии > $c\log n$ переходить на heapsort. Тогда гарантируется худший случай $O(n\log n)$ при сохранении высокой практической скорости.
- Трёх-путевое разбиение (Dutch national flag): при большом числе одинаковых ключей заменить двухчастное разбиение на трёхчастное; при множестве равных ключей даёт время близкое к $O(n)$.
- Усиленный отбор опоры: larger sample (median-of-5 и т.д.), Tukey ninther (медиана медиан) — снижает вероятность плохого разбиения, но увеличивает накладные расходы на выбор опоры.
- Полный детерминированный выбор медианы (median-of-medians) на каждом шаге даёт гарантированно сбалансированный опорный элемент и худший случай $O(n\log n)$, но с заметной константой — редко используют на практике.
- Комбинация практических мер: shuffle + median-of-three (или ninther) + three-way partition + introsort — широко применимый подход (именно так устроен e.g. std::sort в некоторых реализациях).
Краткие рекомендации
- Для практических задач: перемешать вход (или использовать случайный выбор опоры) и introsort — это даёт гарантии и хорошую скорость.
- Если ожидаются много одинаковых ключей — использовать трёхпутевое разбиение.
- При строгих теоретических требованиях на худший случай — использовать median-of-medians или introsort (практически предпочтителен introsort).