java.util.DualPivotQuickSort does not guarantee NlogN time
Joseph D. Darcy
joe.darcy at oracle.com
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
> 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
> 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
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" 
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.
 SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 29(0), 1–4 (0 1999)
More information about the core-libs-dev