On Thu, Jun 2, 2022 at 8:33 PM John Naylor <john.naylor@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
