java.util.DualPivotQuickSort does not guarantee NlogN time

[Buis, Paul]

The slowdown would be passing a single extra integer parameter, decrementing it and comparing it to zero at the beginning of the function.

With an initial value of 4*logN, heapsort would hardly ever be called in practice, only after a long series of unfortundate pivot choices that indicate the data was pathological. The original paper of IntroSort suggested an initial value of 2*logN which triggers the invocation of heapsort just often enough to be noticeable. The proposed threshold should make invocation of heapsort so rare as to not be noticeable.

As the quicksort makes recursive calls, it starts piling on stack space. In a pathological case, taking quadratic time, it may also require linear stack space and throw an exception. Using code that is robust against rare problematic would seem to be appropriate for library code.

Paul Buis