爆速！std::sortを超える「Branchless Quicksort」が爆誕。C/C++ API対応で実装も簡単

std::sortやpdqsortのパフォーマンスを凌駕する、ブランチレス（条件分岐なし）なクイックソートアルゴリズムが登場しました。CおよびC++のAPIが提供されており、既存のプロジェクトにも導入しやすく、ソート処理を極限まで最適化したいエンジニアにとって必見のライブラリです。

すごくシンプルだから、じっくり見ないと理解できなかったよ。見事だね。

ベクトル化されたバイトニックソートネットワークの実装っていくつか存在してない？特にIntelのやつとか。

それと比較しないのはなんで？

（私の古いプロジェクトである）pdqsortの名前が挙がっていたので、その後Lukas Bergdollと共同でRust標準ライブラリ向けに高品質なソート実装であるipnsort（不安定）とdriftsort（安定）を提供したことにも触れておきたい。

というわけで、Rustを使っているなら[T]::sort(_unstable)を呼ぶだけでこれが手に入るよ。最初から素晴らしいパフォーマンスが出るんだ。

自分のマシン（Apple M2）で、Apple clang 17とRust 1.98 nightlyを使ってレポジトリのベンチマークを実行した結果がこれ：

    5000万個のdoubleをソート:
    ipnsort             0.79s
    blqs                0.90s
    driftsort           1.13s   (安定)
    std::sort           1.22s
    std::stable_sort    4.64s   (安定)

    5000万個の(i32, i32)構造体をソート:
    ipnsort             0.82s
    blqs                0.89s
    driftsort           1.07s   (安定)
    std::sort           3.09s
    std::stable_sort    3.15s   (安定)

あと、ちょっとした面白い実験として、5000万個のdoubleの実験をもう一度やってみよう。ただし、最初の90%はすでにソート済みで、最後の10%がランダムな状態にしてみるよ：

    driftsort           0.29s   (安定)
    ipnsort             0.81s
    std::sort           1.15s
    std::stable_sort    1.63s   (安定)
    blqs                1.89s