Yet another Hacker News

22 points signa11 1 day ago 5 comments

brudgers 18 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 1 hour 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 1 hour 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 46 minutes 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.

brudgers 5 minutes ago | parent

[delayed]

omoikane 25 minutes 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)