2.2.1.7 — гибрид за std::sort: три алгоритма, каждый страхует слабость предыдущего2.2.1.7 — the hybrid behind std::sort: three algorithms, each hedging the previous one's weakness
Начинает как quicksort (быстрый средний случай), переключается на heapsort при слишком глубокой рекурсии (страховка от Θ(n²)), переключается на insertion sort для маленьких подмассивов (константы решают на маленьком n). Результат — Θ(n log n) гарантированно, без компромиссов в среднем случае.Starts as quicksort (fast average case), switches to heapsort when recursion gets too deep (a hedge against Θ(n²)), switches to insertion sort for small subarrays (constants win at small n). The result is guaranteed Θ(n log n), with no average-case trade-off.
Ни один из трёх алгоритмов в отдельности не идеален для std::sort: quicksort (2.2.1.4) быстрее всех на практике, но рискует Θ(n²); heapsort (2.2.1.6) гарантированно Θ(n log n), но медленнее на практике из-за кэша; insertion sort (2.2.1.1) быстрее на маленьких n благодаря малым константам, но Θ(n²) на больших. IntroSort использует каждый ровно там, где он лучше остальных, переключаясь между ними по ходу выполнения.None of the three algorithms alone is ideal for std::sort: quicksort (2.2.1.4) is fastest in practice but risks Θ(n²); heapsort (2.2.1.6) guarantees Θ(n log n) but is slower in practice due to cache behavior; insertion sort (2.2.1.1) is faster at small n thanks to small constants, but Θ(n²) at large n. IntroSort uses each exactly where it beats the others, switching between them as it runs.
переключение на heapsort — по глубине рекурсии; переключение на insertion sort — по размеру подмассива, независимо друг от другаswitching to heapsort is triggered by recursion depth; switching to insertion sort by subarray size — independently of each other
void introsort(std::vector<int>& a, int lo, int hi, int depth_limit) {
int size = hi - lo + 1;
if (size < 16) { insertion_sort_range(a, lo, hi); return; } // маленький подмассив// small subarray
if (depth_limit == 0) { heapsort_range(a, lo, hi); return; } // рекурсия зашла слишком глубоко// recursion went too deep
int p = partition(a, lo, hi); // иначе — обычный шаг quicksort// otherwise — a regular quicksort step
introsort(a, lo, p - 1, depth_limit - 1);
introsort(a, p + 1, hi, depth_limit - 1);
}
// вызов: introsort(a, 0, n-1, 2*log2(n))// call: introsort(a, 0, n-1, 2*log2(n))Лимит глубины 2·log₂n выбран не произвольно: у сбалансированного quicksort глубина рекурсии — Θ(log n), значит превышение этого лимита в два раза — надёжный сигнал, что разбиения идут крайне несбалансированно (кандидат на Θ(n²)), и стоит подстраховаться переключением на гарантированный heapsort, не дожидаясь фактического квадратичного поведения.The depth limit of 2·log₂n isn't arbitrary: a balanced quicksort has recursion depth Θ(log n), so exceeding that limit by a factor of two is a reliable signal that partitioning is going badly unbalanced (a Θ(n²) candidate), and it's worth hedging by switching to guaranteed heapsort before quadratic behavior actually materializes.
Оранжевая рамка — активный отрезок [lo, hi]. Цвет заливки говорит, какая стратегия применена к отрезку: синий — quicksort как обычно, жёлтый — переключение на heapsort (глубина рекурсии превысила 2·log₂n), фиолетовый — переключение на insertion sort (отрезок короче 16... здесь для наглядности используется порог 4). Heapsort и insertion sort доводятся до конца одним шагом — их собственная механика уже разобрана на страницах 2.2.1.6 и 2.2.1.1.The orange outline is the active [lo, hi] segment. The fill color shows which strategy was applied: blue — quicksort as usual, yellow — switched to heapsort (recursion depth exceeded 2·log₂n), purple — switched to insertion sort (segment shorter than 16... a threshold of 4 is used here for visibility). Heapsort and insertion sort are each finished in a single step — their own mechanics are covered in detail on pages 2.2.1.6 and 2.2.1.1.
нажмите «Вперёд» или «Играть», чтобы начатьpress "Forward" or "Play" to begin
Обе основные реализации C++ используют вариант IntroSort — именно поэтому std::sort не гарантирует стабильность: гибрид жертвует ей ради средней скорости и гарантированного худшего случая одновременно.Both major C++ implementations use a variant of IntroSort — exactly why std::sort doesn't guarantee stability: the hybrid trades it away for average speed and a guaranteed worst case at once.
Использует IntroSort по тем же причинам, что и C++ — сортировка примитивов не требует стабильности, поэтому выбор смещён в сторону сырой производительности с гарантией худшего случая, а не сохранения относительного порядка.Uses IntroSort for the same reasons as C++ — sorting primitives doesn't require stability, so the choice leans toward raw performance with a worst-case guarantee rather than preserving relative order.