Конспект: Timsort, powersort, introsort и pdqsort

TIMSORT: ПРОХОД
серия: сравнить два первых; убывает - пока строго меньше, развернуть
короткая серия -> до minrun вставками (сравнений log₂, сдвиги дешёвы)
minrun = старшие 6 битов n (+1, если отброшена единица); n < 64 -> n
2112 -> 33 (64 серии), 10⁶ -> 62 (16 130 серий, чуть меньше 2¹⁴)
sorted на 10⁵: готовые - 99 999 сравнений; случайные - 1 528 982
нижняя граница log₂ 100000! ≈ 1 516 704 - перерасход 0,8%

СЛИЯНИЕ
только соседей: иначе ломается устойчивость
обрезка краёв: начало A ≤ B[0] и хвост B ≥ A[-1] уже на месте
буфер - на меньшую часть; при равенстве берётся элемент A
галоп после 7 побед подряд: кусок k за 2⌊log₂ k⌋ + 2 сравнения
проигрывает при k = 2 и 4, выигрывает с k = 6; порог плавает
две серии блоками по 100: 27 992 сравнения на слияние вместо ~200 000

ПОРЯДОК СЛИЯНИЙ
цена слияния = сумма длин
до 3.11: len[-3] > len[-2] + len[-1], len[-2] > len[-1]
  2015: проверяли 3 верхних -> инвариант рушился глубже, Java падала
с 3.11: powersort - сливать на стеке всё с силой > силы новой границы
гарантия powersort: ≤ n·H + 2n, n·H = Σ ℓᵢ log₂(n / ℓᵢ)
[1, 200, 200, 2, 2]: слева 1410, старое 1211, powersort = оптимум 814
[200, 5, 3, 200]: старое = оптимум 624, powersort 816
оптимум при известных длинах: динамика O(r³), Ху - Таккер O(r log r)

БЫСТРАЯ СО СТРАХОВКАМИ
противник Макилроя (1999): ломает быструю с дешёвым детерм. опорным
медиана трёх, n = 200: случайные 1574, убийца 10 135, с защитой 4664
introsort (libstdc++): запас 2⌊log₂ n⌋ -> пирамидальная; куски ≤ 16 -
  вставками одним проходом в конце
pdqsort: плохое разбиение (< 1/8) -> перемешать; > log₂ n плохих ->
  пирамидальная; без обменов -> добить вставками; блоки без ветвлений

КТО ЧТО ИСПОЛЬЗУЕТ
CPython     sorted, list.sort       Timsort + powersort, устойчиво
C++         std::sort               introsort; stable_sort - слиянием
Java        объекты / примитивы     Timsort / двухопорная быстрая
Go 1.19+    sort.Sort               pdqsort
Rust 1.81+  sort / sort_unstable    driftsort / ipnsort