New portion of improvements for Dual-Pivot Quicksort

[Joshua Bloch]

Vladimir,

On Wed, May 5, 2010 at 12:57 AM, Joshua Bloch <jjb at google.com> wrote:

>
> The sentinel technique that you use in lines 118 - 136 is questionable: you
> are modifying a portion of the array outside the specified range of the
> call, which arguably violates the contract of the call, and could be
> observed in a multithreaded program. It's not beyond the realm of reason
> that it could break existing clients. I will discuss it with Doug Lea and
> let you know what he says.
>

I talked to Doug, and he agrees that it's not acceptable to modify any
location outside the array range that the caller has asked you to sort.
 This doesn't entirely kill the optimization; it's still OK to use on
subranges that don't include the first element of the range that you were
asked to sort.  In other words, this test

>
>
 120             if (left > 0) {

Should be replaced by:

 120             if (left > fromIndex + 1) {

and you have to pass original fromIndex down to the recursive calls (in
fact, you could pass fromIndex +1 to avoid the cost of the addition in each
test). It's not clear whether the cost of passing this index down through
the recursive calls will eliminate the gains of the optimization, but it's
worth performing the experiment.

    Sorry,

    Josh
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20100505/684719ba/attachment.html>