Fable 5.2 attempted a Lean proof and found a bug in the implementation, it has a fix though:
The published blqsort has a bug. In partition, the last loop in the C code only skips elements that are greater than or equal to the pivot. It assumes nothing unsorted is left, and that is false.
For example, take 2000 ones with x[1] = 2 and x[2] = 0. The C code returns 0 2 1 1 …, which is not sorted. It fails on about 3 of 4 random seeds.
In a C fuzz test of 20,000 random cases, 904 failed. The C++ and threaded versions have the same loop.
Because of this bug, no proof can show the published code is correct.
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.
> Even though merge sort is algorithmically faster.
Merge sort is algorithmically faster only when either quicksort is implemented naively (in the O(n²) way, which I would obviously ignore) or when data is already almost sorted (when using something more similar to timsort). In the latter case it will be faster even when the data size becomes pretty big, because merge sort will actually reduce memory movements in those cases.
Fable 5.2 attempted a Lean proof and found a bug in the implementation, it has a fix though:
The published blqsort has a bug. In partition, the last loop in the C code only skips elements that are greater than or equal to the pivot. It assumes nothing unsorted is left, and that is false.
For example, take 2000 ones with x[1] = 2 and x[2] = 0. The C code returns 0 2 1 1 …, which is not sorted. It fails on about 3 of 4 random seeds.
In a C fuzz test of 20,000 random cases, 904 failed. The C++ and threaded versions have the same loop.
Because of this bug, no proof can show the published code is correct.
https://github.com/chkas/blqsort/issues/4
[dead]
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.
Sorry for not being clear.
Because overhead is only a few pointers, you can make maximum use of the fastest memory for the items.
It’s why once data gets to an interesting size, it tends tobe quicker than merge sort in practice even though merge sort is algorithmically faster.
> Even though merge sort is algorithmically faster.
Merge sort is algorithmically faster only when either quicksort is implemented naively (in the O(n²) way, which I would obviously ignore) or when data is already almost sorted (when using something more similar to timsort). In the latter case it will be faster even when the data size becomes pretty big, because merge sort will actually reduce memory movements in those cases.
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.
quicksort worst case space bound is still O(logN) as you can tail call on the longest partition and need to maintain a stack only for the other one.
Yes. That isn't textbook quicksort. Ie, the Hoare or Lomuto quicksorts recurse both sides. [1]
But it is a sensible improvement.
(EDIT: I typoed my original comment. It O(n^2) space; worst case is O(n) space and O(n^2) time for the vanilla alg.)
[1] https://en.wikipedia.org/wiki/Quicksort