Replacement of dual-pivot quicksort in java.util.Arrays with new 3-pivot quicksort?

[David McManamon]

Hi,

I found the 2009 discussion and work surrounding dual-pivot quicksort
fascinating.  At that time, 3-pivot quicksort was described as slower;
however, since then a new 3-pivot partition algorithm was published and if
you want the fastest sorting time for primitives then the results are again
very interesting.

For an array with 10 million elements number of swaps switching to
insertion sort at 47 and then not counting swaps:
~74 million 3-pivot quicksort
~74 million dual-pivot quicksort

Yet the 3-pivot is 10-15% faster - cache misses are fewer and so are
comparisons.

Unfortunately as we follow this path some of the original elegance of the
algorithm is lost so I pasted the partition algorithm below for reference.

If you need faster sorting of primitives then run the code:

https://github.com/dmcmanam/quicksort/blob/master/src/Quicksort.java

And just uncomment the Arrays.sort line to compare against the current
dual-pivot you are using.

--David





// Pointers a and b initially point to the first element of the array while
c
// and d initially point to the last element of the array.
int a = lo + 2;
int b = lo + 2;
int c = hi - 1;
int d = hi - 1;
while (b <= c) {
while (A[b] < q && b <= c) {
if (A[b] < p) {
swap(A, a, b);
a++;
}
b++;
}
while (A[c] > q && b <= c) {
if (A[c] > r) {
swap(A, c, d);
d--;
}
c--;
}
if (b <= c) {
if (A[b] > r) {
if (A[c] < p) {
swap(A, b, a); swap(A, a, c);
a++;
} else {
swap(A, b, c);
}
swap(A, c, d);
b++; c--; d--;
} else {
if (A[c] < p) {
swap(A, b, a); swap(A, a, c);
a++;
} else {
swap(A, b, c);
}
b++; c--;
}
}
}
// swap the pivots to their correct positions
a--; b--; c++; d++;
swap(A, lo + 1, a);
swap(A, a, b);
a--;
swap(A, lo, a);
swap(A, hi, d);