Алгоритмы разбиения

Схемы partition: Lomuto (простая, два указателя i/j, элементы ≤pivot слева, O(n) свопов в худшем случае), Hoare (оригинальная 1962, два указателя с концов навстречу, меньше свопов — в 3 раза быстрее Lomuto на практике), DNF (Dutch National Flag, трёхсторонняя partition Дейкстры 1976 для трёх цветов флага Нидерландов). In-place partition O(1) память vs stable partition O(n) память с сохранением порядка равных элементов