Quicksort

Выбирается один элемент (pivot), затем массив переставляется так, чтобы все элементы меньше pivot оказались слева от него, а все большие — справа (сам pivot встаёт на итоговую позицию, где будет находиться в отсортированном массиве). Дальше рекурсия применяется отдельно к левой и правой части — pivot в дальнейшей сортировке не участвует, потому что его позиция уже финальна. В отличие от merge sort, вся работа алгоритма происходит до рекурсивных вызовов (разбиение), а не после (слияние) — поэтому дополнительный массив для объединения результатов не нужен.One element (the pivot) is chosen, then the array is rearranged so every element smaller than the pivot ends up to its left and every larger one to its right (the pivot itself lands in its final sorted position). Recursion then applies separately to the left and right parts — the pivot takes no further part in sorting because its position is already final. Unlike merge sort, all of the algorithm's work happens before the recursive calls (partitioning), not after (merging) — so no extra array is needed to combine results.

// схема Ломуто: pivot — последний элемент// Lomuto scheme: pivot is the last element
int partition(std::vector<int>& a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; ++j)
        if (a[j] < pivot) std::swap(a[++i], a[j]); // граница "меньше pivot" сдвигается// the "less than pivot" boundary advances
    std::swap(a[i + 1], a[hi]); // ставим pivot на итоговое место// put the pivot in its final spot
    return i + 1;
}

void quicksort(std::vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quicksort(a, lo, p - 1);
    quicksort(a, p + 1, hi);
}

Оранжевая рамка — активный отрезок [lo, hi] текущего вызова. Жёлтая заливка — pivot (последний элемент отрезка). Красная рамка — элемент a[j], сравниваемый с pivot прямо сейчас. Зелёная заливка — элементы, уже стоящие на своём финальном месте.The orange outline is the active [lo, hi] segment of the current call. Yellow fill is the pivot (the segment's last element). The red outline is a[j], the element being compared to the pivot right now. Green fill marks elements already in their final position.

Если pivot каждый раз оказывается медианой остатка, разбиение сбалансировано — T(n) = 2T(n/2) + O(n) → Θ(n log n) по Master Theorem (2.1.2). Если pivot каждый раз оказывается минимумом или максимумом (например, всегда последний элемент на уже отсортированном входе), одна часть разбиения пуста, другая — размера n−1: T(n) = T(n−1) + O(n) → Θ(n²). Между этими крайностями — случайный выбор pivot или медиана трёх (медиана первого, среднего и последнего элементов), которые не гарантируют Θ(n log n) математически строго, но делают adversarial худший случай практически невозможным без знания внутренней реализации алгоритма.If the pivot lands on the remainder's median every time, the split is balanced — T(n) = 2T(n/2) + O(n) → Θ(n log n) by the Master Theorem (2.1.2). If the pivot lands on the minimum or maximum every time (e.g. always the last element on an already-sorted input), one partition is empty, the other size n−1: T(n) = T(n−1) + O(n) → Θ(n²). Between these extremes lie randomized pivot selection or median-of-three (the median of the first, middle, and last elements), which don't strictly guarantee Θ(n log n) mathematically but make an adversarial worst case practically impossible without knowledge of the implementation's internals.