Replacement of Quicksort in java.util.Arrays with Dual-Pivot Quicksort: improvements

Joshua Bloch jjb at
Mon Sep 14 21:30:26 UTC 2009

I don't think Dual Pivot Quicksort for List is necessary or appropriate.
 Recall that Arrays.sort and Collections.sort are defined to be stable
sorts, which Quicksort is not.  Also, I just replaced them with TimSort,
which gives a very healthy performance boost.

I do think it would be an interesting experiment to run Dual Pivot Quicksort
on object reference arrays, and TimSort on primitive arrays, but I don't
think we'll end up putting either into the JDK.


On Mon, Sep 14, 2009 at 1:14 PM, Leonid Geller <lgeller at> wrote:

> Remarkable performance improvements!
> The next step to make this "jdk" material is to implement the DPQ using
> collections and generics. Then offer an API to pass a comparator class or
> insure
> the sortable data structure implements comparable interface.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the core-libs-dev mailing list