On Fri, Jun 3, 2022 at 10:44 AM Peter Geoghegan <p...@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