Replacement of Quicksort in java.util.Arrays with Dual-Pivot Quicksort: improvements
jjb at google.com
Mon Sep 14 14:30:26 PDT 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 feedroom.com> 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
> the sortable data structure implements comparable interface.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the core-libs-dev