Yet another Hacker News

31 points signa11 1 day ago 6 comments

brudgers 19 hours ago | parent

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.

paulddraper 2 hours ago | parent

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.

shiandow 2 hours ago | parent

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.

SkiFire13 1 hour ago | parent

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.

omoikane 1 hour ago | parent

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)

spullara 12 minutes ago | parent

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.