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)
