On Fri, Jun 3, 2022 at 10:44 AM Peter Geoghegan <pg@bowt.ie> wrote:
>
> 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.
I had heard of it but not looked into it deeply. I did read that Java
7 uses dual pivot quicksort for primitives and timsort for objects. I
wasn't sure if dual pivot was not good for objects (which could have
possibly-complex comparators) or if timsort was just simply good for
Java's use cases. It seems accessible to try doing, so I'll look into
that.
--
John Naylor
EDB: http://www.enterprisedb.com