Медиана МедианMedian of Medians

Массив делится на группы по 5 элементов (последняя группа может быть короче). В каждой группе за константное время (сортировка пяти элементов) находится её медиана — получается массив из n/5 медиан. Затем pivot выбирается как медиана этого нового массива — рекурсивно тем же алгоритмом медианы медиан (базовый случай — когда элементов достаточно мало, чтобы просто отсортировать напрямую). Это и даёт название: "медиана медиан", то есть медиана массива, состоящего из медиан групп.The array is split into groups of 5 elements (the last group may be shorter). Each group's median is found in constant time (sorting five elements) — yielding an array of n/5 medians. The pivot is then chosen as that new array's median — recursively, using the same median-of-medians algorithm (the base case is when there are few enough elements to just sort directly). This is where the name comes from: "median of medians," the median of an array made of group medians.

Ключевой факт, дающий гарантию: не менее половины групп имеют медиану ≤ pivot, и в каждой такой группе минимум 3 из 5 элементов (сама медиана и два меньших) тоже ≤ pivot. Итого не менее ⌈n/5⌉/2 · 3 ≈ 3n/10 элементов гарантированно ≤ pivot — и симметрично не менее 3n/10 элементов гарантированно ≥ pivot. Значит после partition вокруг этого pivot ни одна из двух частей не может быть больше 7n/10 — в отличие от quickselect с наивным pivot, где худший случай отсекает лишь один элемент за раз, здесь гарантированно отсекается не менее 3n/10 элементов на каждом шаге.The key fact providing the guarantee: at least half the groups have a median ≤ the pivot, and in each such group at least 3 of 5 elements (the median itself and two smaller ones) are also ≤ the pivot. In total, at least ⌈n/5⌉/2 · 3 ≈ 3n/10 elements are guaranteed ≤ the pivot — and symmetrically at least 3n/10 are guaranteed ≥ the pivot. So after partitioning around this pivot, neither part can exceed 7n/10 — unlike quickselect with a naive pivot, where the worst case cuts off just one element at a time, here at least 3n/10 elements are guaranteed to be cut off at every step.

int median_of_medians_select(std::vector<int>& a, int lo, int hi, int k) {
    while (true) {
        if (lo == hi) return a[lo];

        std::vector<int> medians;                     // медианы групп по 5// medians of groups of 5
        for (int i = lo; i <= hi; i += 5) {
            int sub_hi = std::min(i + 4, hi);
            std::sort(a.begin() + i, a.begin() + sub_hi + 1);  // ≤5 элементов — O(1)// ≤5 elements — O(1)
            medians.push_back(a[(i + sub_hi) / 2]);
        }
        // pivot = медиана медиан, найденная рекурсивно тем же алгоритмом// pivot = median of medians, found recursively by the same algorithm
        int pivot_val = (medians.size() == 1)
            ? medians[0]
            : median_of_medians_select(medians, 0, (int)medians.size() - 1, (int)medians.size() / 2);

        int p = partition_around_value(a, lo, hi, pivot_val);   // найти pivot_val, перенести в конец, partition как обычно// find pivot_val, move to the end, partition as usual
        if (k == p) return a[k];
        else if (k < p) hi = p - 1;
        else lo = p + 1;
    }
}

Массив разбивается на группы по 5 (разделены пробелом); внутри каждой группы элементы сортируются, и медиана (жёлтая) отмечается. Из отмеченных медиан рекурсивно выбирается pivot (оранжевая рамка), затем выполняется обычный partition.The array splits into groups of 5 (separated by a gap); within each group elements are sorted and the median (yellow) is marked. A pivot (orange outline) is recursively picked from the marked medians, then ordinary partitioning runs.

Три слагаемых соответствуют трём частям работы: T(n/5) — рекурсивный поиск медианы среди n/5 групповых медиан; T(7n/10) — рекурсивный вызов на большей из двух частей после partition (гарантированно не более 7n/10, как показано выше); O(n) — линейная работа на сортировку групп по 5 и сам partition. Хотя сумма n/5 + 7n/10 = 9n/10 меньше n, это не очевидно даёт линейность без проверки — доказывается индукцией: если T(m) ≤ cm для всех m < n, то T(n) ≤ c(n/5) + c(7n/10) + O(n) = c(9n/10) + O(n), что ≤ cn при достаточно большой константе c, поглощающей O(n)-слагаемое. Это метод подстановки из 2.1.2, применённый к рекуррентности с двумя различными по размеру рекурсивными вызовами вместо одного.The three terms correspond to three parts of the work: T(n/5) — the recursive median search among n/5 group medians; T(7n/10) — the recursive call on the larger of the two parts after partitioning (guaranteed at most 7n/10, as shown above); O(n) — the linear work of sorting groups of 5 and the partition itself. Although the sum n/5 + 7n/10 = 9n/10 is less than n, this doesn't obviously give linearity without checking — it's proven by induction: if T(m) ≤ cm for all m < n, then T(n) ≤ c(n/5) + c(7n/10) + O(n) = c(9n/10) + O(n), which is ≤ cn for a sufficiently large constant c absorbing the O(n) term. This is the substitution method from 2.1.2, applied to a recurrence with two differently-sized recursive calls instead of one.

Почему группы именно по 5, а не по 3 или 7? При группах по 3 доля гарантированно отсекаемых элементов меньше, и рекуррентность решается в Θ(n log n), а не в O(n) — 3 слишком мало для нужной пропорции. При группах по 7 (или больше) пропорция становится ещё выгоднее, но растёт константа на сортировку внутри группы — 5 является наименьшим (и потому самым дешёвым по константе) размером, при котором рекуррентность всё ещё решается линейно.Why groups of exactly 5, not 3 or 7? With groups of 3, the guaranteed-discarded fraction is smaller, and the recurrence solves to Θ(n log n), not O(n) — 3 is too small for the needed proportion. With groups of 7 (or more), the proportion becomes even more favorable, but the constant for sorting within a group grows — 5 is the smallest (and therefore cheapest in constant factor) size for which the recurrence still solves linearly.