Leonid,<div><br></div><div>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.  </div>
<div><br></div><div>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.</div>
<div><br></div><div>           Josh<br><br><div class="gmail_quote">On Mon, Sep 14, 2009 at 1:14 PM, Leonid Geller <span dir="ltr"><<a href="mailto:lgeller@feedroom.com">lgeller@feedroom.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Remarkable performance improvements!<br>
The next step to make this "jdk" material is to implement the DPQ using<br>
collections and generics. Then offer an API to pass a comparator class or insure<br>
the sortable data structure implements comparable interface.<br>
<br>
</blockquote></div><br></div>