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
