Final version of Dual-Pivot Quicksort for replacement quicksort in java.util.Arrays

[Vladimir Iaroslavski]

Hello,

I'd like to provide you the final version of Dual-Pivot Quicksort
for replacement of Quicksort in java.util.Arrays.

Here is the webrev of changes:
http://cr.openjdk.java.net/~alanb/6880672/webrev.02
also you can see classes in attachment.

The following modifications have been done to improve the code
(thank you very much to Josh, Jon and other for your ideas and
suggestions):

1. Implementation of Dual-Pivot Quicksort has been moved to
separate class DualPivotQuicksort.java, it makes Arrays.java more
readable and easy to maintain. If in the future somebody suggests
new very fast Quicksort, the replacement "DualPivotQuicksort.sort(...)"
with "NewVeryFastQuicksort.sort(...)" should be done only in
class Arrays.java.

2. Improved and added javadoc.

3. Method swap(a, i, j) has been eliminated. All sort loops had
the structure:

for (int k = ...; ...) {
   int ak = a[k];
   if (ak < ...) swap(a, k, ..)

This standard method "swap" swaps the values of two elements using
3 assignments, but we already have value of a[k] stored in temporary
local variable ak, so we can do it via 2 assignments only:

a[k] = a[...];
a[...] = ak;

4. Standard implementation of Insertion sort (with swaps inside inner loop)
has been replaced by faster one:

for (int k = left + 1; k <= right; k++) {
     int ak = a[k];
     int j;

     for (j = k - 1; j >= left && ak < a[j]; j--) {
         a[j + 1] = a[j];
     }
     a[j + 1] = ak;
}

5. Insertion sort threshold has been changed to 32.

6. Five candidates, evenly spaced elements, are used for choosing
2 pivots (in previous version only 2 evenly spaced elements are used).

7. These five elements are sorted by sorting network

8. Main sorting loop was separated into two: when pivots are equal and not.

9. Swap of conditions in inner while loop: a[great] > pivot2 && k < great
(was k < great && a[great] > pivot2).

10. Changes in code after main sorting loop: if pivots are equals, no need
to handle and sort central part:

if (!pivotsDiffer) {
   return;
}

11. Condition of handling central part (looking of elements, equal to pivots,
and swap them to ends) has been simplified:

if (less < e1 && e5 < great) ... instead of
if (dist > len - 13 && pivot1 != pivot2)

12. Loop of handling central part has been corrected and updated.

13. Parameter "dist" has been eliminated.

Also I'd like to show you how the new version works faster.
I run two versions against current jdk's implementation
on jdk 1.7.0-ea-b66, Windows XP. The test framework is
Bentley's tests which were used for testing Quicksort.
I run for arrays with length = 1'000'000 and calculated
arithmetics and geometric means:

                     Client VM                       Server VM

old version: arithm = 81.78%, geom = 76.15%  arithm = 91.97%, geom = 72.58%
new version: arithm = 74.71%, geom = 65.95%  arithm = 64.54%, geom = 54.21%

Thank you,
Vladimir
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: Arrays.java
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20091019/faf1859e/Arrays.java>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: DualPivotQuicksort.java
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20091019/faf1859e/DualPivotQuicksort.java>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: DualPivotQuicksort_old.java
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20091019/faf1859e/DualPivotQuicksort_old.java>