On Thu, Jun 2, 2022 at 8:33 PM John Naylor <john.nay...@enterprisedb.com> wrote: > Attached is a draft series that implements some but not all features > of pattern-defeating quicksort, namely the ones I thought were > interesting for us. Recently this quicksort variant got committed for > the next release of the Go language 1.19 [1] (which in turn was based > on that of Rust [2]), and that implementation was a helpful additional > example. The bottom line is that replacing the partitioning scheme > this way is likely not worth doing because of our particular use > cases, but along the way I found some other things that might be worth > doing, so some good may come out of this.
What about dual-pivot quicksort, which is used in Java 7+? That is the defacto successor to Bentley & McIlroy. In fact, Jon Bentley himself collaborated with its author, and provided benchmarking input. The underlying philosophy is essentially the same as the original -- it is supposed to be an "industrial strength" quicksort, with various adversarial cases considered directly. See: https://www.wild-inter.net/publications/wild-2018b.pdf https://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf At one point quite a few years back I planned on investigating it myself, but never followed through. -- Peter Geoghegan
