Кристоф Казер опубликовал blqsort — реализацию быстрой сортировки, написанную полностью без условных переходов. Идея в том, чтобы избавиться от if в горячих циклах: на современных CPU промахи предсказания ветвлений стоят дороже, чем лишние операции с памятью. blqsort использует branchless partitioning — вместо проверки условия движок по индексному массиву или буферу решает, куда положить элемент, не прерывая конвейер.
Бенчмарки на 50 миллионах double: на Apple M1 (Clang) blqsort сортирует за 0.97 секунды против 1.33 у std::sort и pdqsort. На AMD Ryzen (GCC) — 2.06 секунды против 5.56 у std::sort и 2.81 у pdqsort. Многопоточная версия на M1 ещё в три-четыре раза быстрее.
Алгоритм копирует 1024 элемента в стековый буфер (не в кучу) и поочерёдно раскладывает блоки налево и направо от пивота — без единого if. Это требует вдвое больше копий, но для дешёвых типов это всё равно выгоднее, чем промахи предсказания.
Чтобы избежать О(n²) на плохих данных, blqsort группирует одинаковые элементы, при сильном дисбалансе переключает конкретный участок на heapsort и проверяет, не отсортирован ли массив. Для поиска пивота используется median-of-medians. Критические циклы явно развёрнуты. Для 2–12 элементов — кастомные sorting networks, написанные branchless-примитивом sort-2.
Для типов с высокими затратами на копирование (вроде строк, не is_trivially_copyable) библиотека переключается на BlockQuicksort (Edelkamp & Weiß) — там безусловно обрабатываются только индексы, а сами данные перекладываются реже.
API минимален. В C++ достаточно подключить blqs.h и вызвать blqs::sort(data, data + SIZE). Многопоточная C++-версия — blqs_thr.h. В C — #define BLQS_TYPE double, #include "blqsort.h" и вызов blqsort(data, SIZE). Многопоточная C-версия — blqsort_thr.h (на POSIX threads). blqsort легко сортирует пользовательские структуры с кастомным компаратором — в отличие от SIMD-библиотек вроде Google Highway, которые на таких задачах бесполезны.
На 50 миллионах структур с двумя int полями blqsort на M1 выдаёт 0.96 секунды (против 3.46 у std::sort), на AMD — 2.20 (против 4.75). Исходники — на GitHub.