arXiv:2106.05123cs.DS
A new solution for the Dutch national flag problem is proposed, requiring no three-way comparisons, which gives quicksort a proper worst-case runtime of $O(nk)$ for inputs with $k$ distinct elements. This is used together with other known and novel techniques to construct a hybrid sort that is never significantly slower than regular quicksort while speeding up drastically for many input distributions.
Linked by 3 identifiable commenters in 3 comments across 3 threads, from Jul 2021 to Jun 2023.
Theoretical advances are constant (just check the literature), but two particular advances in the last decade are of practical importance: one for sort and one for hash table. As in: check the implementation you are using, if it doesn't incorporate these advances you are leaving…
This article is missing the important reference to the prior work by Edelkamp and Weiss, on branchless quicksort [1]. I've long since implemented that in pdqsort [2], along with other techniques described by me in [3] which is a drop-in replacement for std::sort that's ~twice as…
Connected through shared HN threads, not inferred similarity or a recommendation.
pdqsort paper: https://arxiv.org/abs/2106.05123 fluxsort compiles in C++ just fine. Pre-sorted data is just the simplest example of adaptivity. Partially-sorted input can't be tracked easily by the caller and I believe that something like merging a few sorted arrays by…
mlochbaumView on HNParent context