java.util.DualPivotQuickSort does not guarantee NlogN time

[Joseph D. Darcy]

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

     http://www.sonic.net/~jddarcy/Research/cs339-quicksort.pdf

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.

-Joe

[1] SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 29(0), 1–4 (0 1999)