Patch to improve primitives Array.sort()

[Chan, Sunny]

We are proposing a patch to improve the performance for the DualPivotQuickSort use by Array.sort to sort primitives array. We have identified two area for optimization:

Firstly, we have changed the algorithm to determine what a "run" is. A "run" is how long you go through the array with it being in order. For example, an array of 1, 2, 3, 5, 4, 3 would have a run count equal to 2 (two parts that are in order).

The JDK implementation stops looking for runs if it comes across two equal numbers at the beginning of a run, eg.
1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 5
And then sorts the whole array, as seen in this part of the algorithm:
} else { // equal
    for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
        if (--m == 0) {
            sort(a, left, right, true);
            return;
        }
    }
}

Instead, we detect and equal beginning of a run at the top of the for loop, as shown here:
while (k < right && a[k] == a[++k]); //equal

so the array mentioned above would instead have one run, be determined already sorted, and sort would not be called as it would in the original JDK implementation.

Second optimization is in the case of an array that is descending, and then ascending.

Since the algorithm does swapping in the case of descending numbers, by the end of all swapping the array is sorted. We detect this through this if statement:
if (run[count] > left && a[run[count]] >= a[run[count] - 1]) {
    count--;
}
And will stop sorting, unlike the JDK.

I have attached a webrev.zip containing the patch and unit test that verifies the sort is correct. We also have a couple of JMH based performance tests which is not included. If the JMH is available we can also make those performance test available as well.

The patch is author by Kristen O'Leary (Kristen.o'leary at gs.com) and myself. Please attribute both of us when committing. You can find my OCA entry under Goldman Sachs and as we are not authors yet we can't raise a bug report in the database.

Please let us know if you need further clarification or modification to the patch.

Sunny Chan, Executive Director, Technology
Goldman Sachs (Asia) L.L.C. | 68th Floor | Cheung Kong Center | 2 Queens Road Central | Hong Kong
email:  sunny.chan at gs.com | Tel: +852 2978 6481 | Fax: +852 2978 0633

This message may contain information that is confidential or privileged.  If you are not the intended recipient, please advise the sender immediately and delete this message.  See http://www.gs.com/disclaimer/email for further information on confidentiality and the risks inherent in electronic communication.