Previously:

https://news.ycombinator.com/item?id=48375445 - Branchless Quicksort faster than std:sort and pdqsort with C and C++ API (2026-06-02, 82 comments)

Quicksort is quick because it's space requirements are not just linear but very very close to n. It is quick because it minimizes IO.

To be clear I did not look at the code, but benchmarking against 50 million items makes me suspect that minimal IO was required.

Now sure, sometimes that is exactly your use case. But for many interestingly sized problems, IO dominates.

That's one of the reasons radix sort is terribly quick when applicable (and a lot of orderings are lexicographic). It's effectively just a few scans over the data. I suppose the simplest version does make a copy of the data but it has excellent locality of reference.

Quicksort is quick because it's space requirements are very far from _n_, as they are just O(log n).

A fast sorting algorithm whose space requirements are closer to n would be e.g. merge sort.

If you use O(log n) space you are doing IO because n items requires n memory so most of your items are sitting someplace slow.

Quicksort requires n+c space where c is a few pointers.

https://www.cs.ox.ac.uk/files/6226/H2006%20-%20Historic%20Qu...

It's an in-place sort with extra space O(log n). Same as quicksort average, better than quicksort worst O(n^2).

This uses a bunch of low-level tricks and alternate stragies to beat std::sort on random data.

The primary advantage is branchless partitioning, which is a big win for random data, which hurts branch prediction for quicksort.