java.util.DualPivotQuickSort does not guarantee NlogN time
dl at cs.oswego.edu
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