java.util.DualPivotQuickSort does not guarantee NlogN time

[Buis, Paul]

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.