java.util.DualPivotQuickSort does not guarantee NlogN time

[Doug Lea]

On 01/26/2015 03:05 PM, Buis, Paul wrote:
> 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.

I was only tangentially involved with this, but I believe that
this was considered and rejected because the patterns leading
to quadratic performance practically never occur -- why slow
down an algorithm to handle (nearly) non-existent cases.
But if there were ever any evidence otherwise, this would be
worth considering.

BTW, over the past few years, there have been some academic papers
investigating why DPQS is even faster than expected. (See for example
http://epubs.siam.org/doi/pdf/10.1137/1.9781611973198.6 and
http://arxiv.org/pdf/1412.0193v1.pdf) It seems that cache locality
is one factor. This would not be helped if heapSort were
unnecessarily called, since it has terrible cache locality.

-Doug