Ниже — краткое, но практически полное руководство по рекурсивной реализации быстрой сортировки (quicksort), её сложностям, причинам деградации и проверенным приёмам для повышения устойчивости на реальных данных.

1) Рекурсивная реализация (базовая, 2‑way partition)
Псевдокод (использует разделение Lomuto/Hоare; здесь — простая версия с выделением опорного и стандартным partition):

function QuickSort(A, lo, hi)
if lo >= hi then return
p := ChoosePivot(A, lo, hi) // например, A[lo] или случайный элемент
Swap(A, p, hi) // поместить опорный в конец (для Lomuto)
pivotIndex := PartitionLomuto(A, lo, hi)
QuickSort(A, lo, pivotIndex - 1)
QuickSort(A, pivotIndex + 1, hi)

function PartitionLomuto(A, lo, hi)
pivot := A[hi]
i := lo
for j from lo to hi-1
if A[j] <= pivot
Swap(A, i, j)
i := i + 1
Swap(A, i, hi)
return i

Замечания:

ChoosePivot может возвращать индекс первого/последнего/случайного/median-of-three и т.д.Это простой и наглядный вариант; Lomuto прост, но делает больше обменов. Hoare partition обычно быстрее и делает меньше обменов, но требует аккуратной реализации индексов.

2) Альтернатива для многих равных ключей — 3‑way (Dutch National Flag)
Если в данных много повторяющихся значений, эффективнее 3‑way разделение:

function QuickSort3(A, lo, hi)
if lo >= hi then return
pivot := ChoosePivot(A, lo, hi)
Swap(A, pivot, lo) // опорный в A[lo]
lt := lo; i := lo + 1; gt := hi
while i <= gt
if A[i] < A[lt]
Swap(A, lt, i); lt := lt + 1; i := i + 1
else if A[i] > A[lt]
Swap(A, i, gt); gt := gt - 1
else
i := i + 1
QuickSort3(A, lo, lt - 1)
QuickSort3(A, gt + 1, hi)

3) Временные сложности

Средняя (ожидаемая) сложность: O(n log n). Именно при случайных (или «в среднем» по всем перестановкам) разбиениях рекурсия дает глубину ~log n и суммарную линейную работу на каждом уровне.Худшая сложность: O(n^2). Происходит при сильно неравных разбиениях, например, когда опорный всегда оказывается минимальным/максимальным и один из подмассивов пуст, другой размер ~n-1.

4) В каких случаях алгоритм деградирует до O(n^2)

Плохой выбор опорного: всегда первый/последний элемент и вход уже (или почти) отсортирован => последовательные разбиения размером n-1 и т.д.Адаптивный или злонамеренный ввод (адверсарный): если вход сконструирован в соответствии с стратегией выбора опорного.Большое количество равных ключей при использовании стандартного 2‑way partition — тогда разбиения не уменьшают размер значительно.Отсутствие рандомизации и специальных защитных приёмов.

5) Практические приёмы для повышения устойчивости и производительности

a) Случайная перестановка (random shuffle)

Перетасуйте массив перед сортировкой (Fisher–Yates). Простая и эффективная защита от входа, специально выбранного против алгоритма.Стоимость O(n) одного раза, затем обычный quicksort со статистически хорошим поведением.

b) Случайный выбор опорного (random pivot)

На каждой рекурсии выбирать случайный элемент как опорный. Устраняет зависимость от порядка входа (стохастически). Нужна генерация случайных чисел.

c) median-of-three / median-of-k / Tukey’s ninther

Выбирать медиану из трёх (первая, средняя, последняя) — простая эвристика для уменьшения шансов плохого разбиения на почти отсортированных данных.Для больших массивов используют медиану из k (напр., "ninther": медиана трёх медиан по 3 элементов) — лучше приближает медиану, но дороже выбирать.median-of-medians (детерминированная) гарантирует хорошую медиану и теоретическую линейную сложность разделения, но высокая константа делает её редко используемой в практических quicksort.

d) 3‑way partitioning (Dutch flag)

Если в данных много одинаковых ключей, 3‑way быстро выделяет равные участки и предотвращает деградацию. Часто значительно быстрее для слабо отличающихся элементов.

e) Переключение на insertion sort для маленьких подмассивов

Для маленьких n (например, n ≤ 16..32) insertion sort/пузырёк/selection выполняются быстрее из‑за низких констант.Практическая стратегия: рекурсию обрываем при пороге и применяем insertion sort в конце.

f) Tail recursion elimination / рекурсивное всегда на меньшую часть

Всегда рекурсивно обрабатывать меньшую часть стека, а для большей — использовать цикл (tail recursion elimination). Это гарантирует глубину рекурсии O(log n) в лучшем/среднем случае и уменьшает риск переполнения стека.Псевдокод:

function QuickSortTail(A, lo, hi)
while lo < hi
p := partition(...)
if p - lo < hi - p
QuickSortTail(A, lo, p-1)
lo := p+1 // цикл вместо рекурсии на большой части
else
QuickSortTail(A, p+1, hi)
hi := p-1

g) Ограничение глубины рекурсии + Introsort (гибрид)

Introsort: начать с quicksort (обычно с median-of-three), но если глубина рекурсии превышает порог (обычно 2*log2(n)), переключиться на heapsort для текущего подмассива — это даёт гарантированный O(n log n) худший случай и сохраняет быстроту quicksort в среднем.Introsort — стандарт в некоторых библиотеках (например, C++ std::sort использовал эту идею).

h) Dual‑pivot quicksort

Вариант с двумя опорными (используется в Java 7+), который в некоторых реализациях даёт меньше сравнений и лучше кэш-локальность; но сложнее реализовать и не всегда лучше на всех входах.

i) Детектирование и защита от подозрительных входов

Например, If many partition levels are very unbalanced in a short time, переключиться на другой метод (перетасовать, использовать другой выбор опорного, или перейти к heapsort).

j) Стабильность и память

Быстрый сорт in‑place, но нестабилен. Если нужна стабильность, используют дополнительные структуры (merge sort или stable quicksort с дополнительной памятью).

6) Практическая комбинация (рецепт)
Хорошая практическая реализация для общего назначения:

Случайно перетасовать данные или использовать случайный/median-of-three pivot.Использовать 3‑way partition если возможны дубликаты.Порог перехода на insertion sort ≈ 16..32.Устранять хвостовую рекурсию (recurse on smaller partition).Ограничивать глубину и переходить на heapsort (Introsort) при слишком большой глубине.
Эта комбинация даёт высокую скорость в среднем и защиту от O(n^2).

7) Простые рекомендации для практической реализации

Если нужно простая и надёжная: используйте std::sort (C++) или готовую библиотечную функцию — обычно это introsort/гибрид с оптимизациями.Если вы пишете свою: реализуйте median-of-three, tail recursion elimination, cut‑off to insertion sort, и опционально переключение на heapsort при большой глубине.Для массивов с множественными равными ключами обязательно 3‑way partition.

Короткое резюме

Quicksort: отличный в среднем (O(n log n)), но при плохом выборе опорного может стать O(n^2).Устранение деградации: рандомизация/median-of-three/Tukey‑ninther, 3‑way partition для дубликатов, tail recursion elimination, cut‑off to insertion sort, и гибриды вроде introsort (fallback to heapsort) — все вместе дают устойчивую и быструю сортировку на реальных данных.