Новый C++-алгоритм blqsort обгоняет std::sort почти вдвое
A C++ Quicksort Faster Than std:sort
Автор blqsort утверждает, что не знает другого универсального алгоритма сортировки на основе сравнений, который был бы быстрее на случайных данных — кроме специализированных SIMD-решений для примитивов. На 50 миллионах случайных doubles на Apple M1 blqsort справляется за 0,68 с против 1,33 с у std::sort, а на Intel i5-9300H — за 1,32 с против 4,02 с. Секрет — ветвление без ветвей, сортирующие сети для малых партиций и продуманный выбор опорного элемента. Код под MIT, есть и C-версия.
Компилятор не знает природы ваших данных. Если бы лишь малая доля чисел была меньше 500, версия с ветвлением могла бы оказаться быстрее, потому что предсказатель почти всегда угадывал бы.
- spullara
Fable 5.2 попытался построить доказательство в Lean и нашёл баг в реализации, впрочем, исправление уже есть:
В опубликованном blqsort есть баг. В partition последний цикл в C-коде пропускает только элементы, которые больше или равны опорному. Он предполагает, что неотсортированных элементов не осталось, и это неверно.
Например, возьмём 2000 единиц с x[1] = 2 и x[2] = 0. C-код возвращает 0 2 1 1 …, что не отсортировано. Он падает примерно на 3 из 4 случайных сидов.
В C-фазз-тесте из 20 000 случайных случаев 904 провалились. В C++ и многопоточной версиях тот же цикл.
Из-за этого бага никакое доказательство не может показать, что опубликованный код корректен.
- omoikane
Ранее:
https://news.ycombinator.com/item?id=48375445 — Branchless Quicksort быстрее std:sort и pdqsort с C и C++ API (2026-06-02, 82 комментария)
- brudgers
Quicksort быстрый потому, что его требования к памяти не просто линейны, а очень-очень близки к n. Он быстрый потому, что минимизирует IO.
Чтобы было ясно, я не смотрел код, но бенчмарк на 50 миллионов элементов заставляет меня подозревать, что минимальный IO был необходим.
Конечно, иногда это именно ваш случай. Но для многих задач интересного размера IO доминирует.