30 points by signa11 1 day ago
Comments are read-only. Visit Hacker News to participate in the discussion.
omoikane 1 hour ago | 0 points
Previously:<p><a href="https://news.ycombinator.com/item?id=48375445">https://news.ycombinator.com/item?id=48375445</a> - Branchless Quicksort faster than std:sort and pdqsort with C and C++ API (2026-06-02, 82 comments)
brudgers 19 hours ago | 0 points
Quicksort is quick because it's space requirements are not just linear but very very close to <i>n</i>. It is quick because it minimizes IO.<p>To be clear I did not look at the code, but benchmarking against 50 million items makes me suspect that minimal IO was required.<p>Now sure, sometimes that is exactly your use case. But for many interestingly sized problems, IO dominates.
shiandow 1 hour ago | 0 points
That's one of the reasons radix sort is terribly quick when applicable (and a <i>lot</i> 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 | 0 points
Quicksort is quick because it's space requirements are very far from _n_, as they are just O(log n).<p>A fast sorting algorithm whose space requirements are closer to n would be e.g. merge sort.
paulddraper 1 hour ago | 0 points
It's an in-place sort with extra space O(log n). Same as quicksort average, better than quicksort worst O(n^2).<p>This uses a bunch of low-level tricks and alternate stragies to beat std::sort on random data.<p>The primary advantage is branchless partitioning, which is a big win for random data, which hurts branch prediction for quicksort.