Dieser C++-Quicksort schlägt std::sort deutlich
A C++ Quicksort Faster Than std:sort
blqsort sortiert 50 Millionen zufällige doubles auf einem Apple M1 in 0,68 Sekunden – std::sort braucht 1,33 Sekunden. Auch auf einem Intel i5-9300H liegt blqsort mit 1,32 statt 4,02 Sekunden klar vorn. Der Trick: branchless Partitionierung, Sortiernetzwerke für kleine Partitionen und eine sorgfältige Pivot-Wahl. Der Code steht unter MIT-Lizenz auf GitHub, auch als C-Version mit Multithreading in je einer Header-Datei.
Der Compiler weiß nicht, wie deine Daten beschaffen sind.
- spullara
Fable 5.2 hat einen Lean-Beweis versucht und dabei einen Bug in der Implementierung gefunden, es gibt aber einen Fix:
Der veröffentlichte blqsort hat einen Bug. In der Partition überspringt die letzte Schleife im C-Code nur Elemente, die größer oder gleich dem Pivot sind. Sie geht davon aus, dass nichts Unsortiertes übrig bleibt, und das ist falsch.
Zum Beispiel: 2000 Einsen mit x[1] = 2 und x[2] = 0. Der C-Code liefert 0 2 1 1 …, was nicht sortiert ist. Er scheitert bei etwa 3 von 4 zufälligen Seeds.
In einem C-Fuzz-Test mit 20.000 zufälligen Fällen sind 904 fehlgeschlagen. Die C++- und die Threaded-Version haben dieselbe Schleife.
Wegen dieses Bugs kann kein Beweis zeigen, dass der veröffentlichte Code korrekt ist.
- omoikane
Früher:
https://news.ycombinator.com/item?id=48375445 - Branchless Quicksort schneller als std:sort und pdqsort mit C- und C++-API (2026-06-02, 82 Kommentare)
- brudgers
Quicksort ist schnell, weil sein Platzbedarf nicht nur linear, sondern sehr, sehr nahe an n ist. Es ist schnell, weil es IO minimiert.
Um es klarzustellen: Ich habe mir den Code nicht angesehen, aber der Benchmark gegen 50 Millionen Elemente lässt mich vermuten, dass minimaler IO nötig war.
Klar, manchmal ist das genau dein Anwendungsfall. Aber bei vielen interessant großen Problemen dominiert der IO.