Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

Vadim Ponomarenko vadim123 at
Fri Sep 11 22:48:56 UTC 2009

Vladimir Yaroslavskiy <Vladimir.Yaroslavskiy at ...> writes:
> I'd like to share with you new Dual-Pivot Quicksort which is
> faster than the known implementations (theoretically and
> experimental). I'd like to propose to replace the JDK's
> Quicksort implementation by new one.

This is a great idea; as a mathematician I immediately want to generalize it.
Unfortunately, I lack the computing skill to test my generalization in

Suppose that instead of 2 pivots we have m (randomly chosen) pivots, where
Step 1: Sort the m pivots, recursively.
Step 2: Build a balanced binary tree from the pivots.
Step 3: Sort the remaining n-m elements into (m+1) categories, using the BBT.
Step 4: Sort each of the (m+1) categories, recursively.

Let S(n) denote the number of steps needed for this algorithm.  Calculating
Step 1 requires S(m) steps.
Step 2 requires m steps (it is easy since the pivots are already sorted).
Step 3 requires (n-m)(log m) comparisons.
Step 4 requires, on average, (m+1)S((n-m)/(m+1)) steps.

m was chosen so that (n-m)/(m+1)=m, so S(n)=(m+2)S(m)+m+(n-m)(log m) <= (m+2)
S(m)+ n log m.  Crudely, we replace both m and m+2 by sqrt(n), to get as
S(n) <= 0.5 n log n + n^0.5 [ 0.25 n^0.5 log n + n^0.25 [ 0.125 n^0.25 log n
 +...]]] = 0.5 n log n [1 + 0.5 + 0.25 + ...] = n log n.  This appears to be
better than 2 n log n.  This argument can be made precise (the only really
questionable issue is replacing m+2 by m) by first getting a crude but 
correct upper bound for 2S(m), which gets absorbed into the -mlogm term.

Unfortunately, I'm not up to the detailed comparison vs. swap analysis as 
done by Mr. Yaroslavskiy, but it seems to me that, if nothing else, having 
an efficient algorithm to partition the non-pivot elements should provide a

Vadim Ponomarenko
Dept. of Mathematics and Statistics
San Diego State University

More information about the core-libs-dev mailing list