DualPivotQuickSort is used by Arrays.sort() and provides NlogN average
performance, but does not guarantee NlogN worst case performance. It would be
relatively easy to incorporate the basic idea of IntroSort (see
http://en.wikipedia.org/wiki/Introsort) to provide such a guarantee. To make
this happen, in java.util.DualPivotQuicksort, for each primitive type one need
only keep track of the recursion depth relative to some constant times the log
of the size of what is being sorted. So, for int[], one does something like:
// IntroSort normally uses a DEPTH_FACTOR of 2
private static final int DEPTH_FACTOR = 4;
private static void sort(int[] a, int left, int right, boolean leftmost){
sort(a, left, right, leftmost 0, DEPTH_FACTOR*(31-Integer.
numberOfLeadingZeros(right-left));
}
Then, modify the existing sort to take a couple of extra parameters to keep
track of the recursion depth and if the recursion is going too deep, do a
heapSort to prevent potential for quadratic time performance.
private static void sort(int[] a, int left, int right, boolean leftmost, int
depth, int maxDepth){
if (depth > maxDepth) {
heapSort(a, left, right);
return;
}
...
// replace recursive calls with
sort(a, ... , depth+1, maxDepth)
}
I'd be happy to provide a complete DualPivotQuicksort.java source file with
this implemented if the folks in charge think this is worthwhile.
