Как работает быстрая сортировка и когда она работает медленно?

Схема «разделяй и властвуй»:

1. выбрать опорный элемент (pivot);
2. разбиение (partition): переставить элементы так, чтобы слева были не больше опорного, справа — больше; опорный оказывается на своей итоговой позиции;
3. рекурсивно отсортировать левую и правую части.

Разбиение выполняется на месте за O(n). Две известные схемы: Ломуто — проще, опорный — последний элемент; Хоара — два указателя навстречу, меньше обменов.

Почему O(n log n) в среднем. Если опорный делит массив примерно пополам, глубина рекурсии — log n уровней, на каждом суммарно O(n) работы.

Почему O(n²) в худшем. Если опорный каждый раз минимальный или максимальный, одна часть пустая, а другая меньше всего на один элемент: n уровней по O(n). Классический случай — опорный «последний элемент» на уже отсортированных или почти отсортированных данных. Ещё один — много одинаковых значений при наивном разбиении.

Как защищаются:

• случайный опорный — худший случай становится крайне маловероятным;
• медиана трёх (первый, средний, последний);
• трёхпутевое разбиение для повторов (меньше, равно, больше);
• introsort — при слишком глубокой рекурсии переключение на пирамидальную сортировку, что гарантирует O(n log n).

Быстрая сортировка неустойчива, дополнительная память — O(log n) на стек рекурсии (если сначала рекурсивно обрабатывать меньшую часть).

def quicksort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return
    pivot = a[hi]                      # Ломуто: опорный — последний
    i = lo - 1
    for j in range(lo, hi):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]  # опорный на своё место
    quicksort(a, lo, i)
    quicksort(a, i + 2, hi)