java.util.DualPivotQuickSort does not guarantee NlogN time

Joseph D. Darcy joe.darcy at
Tue Jan 27 23:22:30 UTC 2015

On 1/27/2015 12:15 PM, Doug Lea wrote:
> 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.)

FWIW, long predating the dual pivot work in the JDK, back in 2002 I did 
some work looking into quicksort variants

which included looking over a sample of the many, many quicksort 
variations people have explored.

Germane to the worst case behavior discussion is another paper I recall 
reading at the time, McIlroy's "A Killer Adversary for Quicksort" [1] 
which uses an adversarial comparator in C to force quadratic behavior 
regardless of the pivoting strategy, including randomized pivots.

I assume a similar approach could be used to get worst-case behavior 
with analogous Java library constructs.



More information about the core-libs-dev mailing list