std::sortより速いC++クイックソート、blqsortが登場
A C++ Quicksort Faster Than std:sort
作者が公開したblqsortは、分岐なしのパーティショニング、小規模パーティション向けのソーティングネットワーク、工夫されたピボット選択を組み合わせたクイックソートだ。5000万個のランダムなdoubleのソートで、Apple M1ではstd::sortの1.33秒に対し0.68秒、Intel i5-9300Hでは4.02秒に対し1.32秒と約2〜3倍高速。MITライセンスでC版やマルチスレッド版も単一ヘッダーとして提供されている。
コンパイラはあなたのデータの性質を知らない。500未満の数がごく一部であれば、分岐予測がほぼ常に当たるため、実はif版のほうが速い可能性もある。
- omoikane
以前にも：
https://news.ycombinator.com/item?id=48375445 - Branchless Quicksort faster than std:sort and pdqsort with C and C++ API (2026-06-02、82コメント)
- brudgers
Quicksortが速いのは、その空間要件が単に線形なだけでなく、nに限りなく近いからだ。IOを最小化するから速いのだ。
はっきり言っておくと、私はコードを見ていない。しかし5000万件のアイテムに対してベンチマークを取っているのを見ると、最小限のIOしか必要としなかったのだろうと推測する。
もちろん、それがまさにあなたのユースケースであることもあるだろう。しかし、興味深いサイズの問題の多くでは、IOが支配的になる。