java.util.DualPivotQuickSort does not guarantee NlogN time

Doug Lea dl at
Tue Jan 27 20:15:33 UTC 2015

On 01/27/2015 08:44 AM, Buis, Paul wrote:
> The slowdown would be passing a single extra integer parameter, decrementing it and comparing it to zero at the beginning of the function.

Right. The question is whether even a small slowdown is warranted.
Does quadratic behavior arise more that once per trillion cases?
Or is there some scenario in which worst-case inputs can be crafted in advance?
It's possible that a good case can be made here, but I don't know it.
(So I'm not arguing against doing this, but it requires further justification.)


More information about the core-libs-dev mailing list