# Dual-pivot Quicksort reference implementation?

Has some sort of canonical - or reference - implementation of Dual-pivot Quicksort been posted anywhere?

I would like to include that algorithm in a comparison among sorting algorithms for a specialized need that I have, but the Java versions I've seen appear to have various kinds of tweaks applied to them, like using Insertion Sort for small (sub-) arrays, which makes it harder to compare the fundamentals.

• Insertion Sort for small sub-arrays is fundamental. What matters when choosing between $O(n \lg n)$ sorting algorithms is the constant factors. You can't get an accurate measure of the constant factors if you are wasting gobs of time doing three recursive calls on every 10 element subarray. The implementations should all do tail recursion elimination too. And use a hand-optimized and inlined stack instead of doing the non-tail recursions. Apr 25, 2014 at 1:13
• What would you consider "reference" and what "implementation"? Usually, Sedgewick's thesis would be the go-to reference for Quicksort. But which dual-pivot QS do you mean? There's also the one used in the Java 7 library.
– Raphael
Apr 25, 2014 at 6:57
• @WanderingLogic: "You can't get an accurate measure of the constant factors if..." -- well, you can! It's just that such implementations waste lots of time, but that's part of that ones' runtime.
– Raphael
Apr 25, 2014 at 6:59
• @Raphael: The question was inspired in part by the fact that Java 7 apparently uses this algorithm for general sorting now. I am wondering if the improvements over earlier versions are specific to Java and/or those earlier implementations or if they apply in general, e.g. with a compare function rather than straight ints or with a very high ratio of duplicate keys in the input. Apr 25, 2014 at 8:29
• @500-InternalServerError It's important to say that; there have been other multi-pivot Quicksorts decades ago which are slightly (but significantly) different.
– Raphael
Apr 25, 2014 at 8:31

I tried to do exactly such a comparison in my master thesis, which thus naturally includes pseudo-code of “basic” versions of several dual-pivot Quicksorts (there is a list of them on page 9).

Here is my basic implementation of Yaroslavskiy's algorithm (the dual-pivot scheme that is used in Java 7):

void sort(int[] A, int left, int right) {
if (right > left) {
// Choose outermost elements as pivots
if (A[left] > A[right]) swap(A, left, right);
int p = A[left], q = A[right];

// Partition A according to invariant below
int l = left + 1, g = right - 1, k = l;
while (k <= g) {
if (A[k] < p) {
swap(A, k, l);
++l;
} else if (A[k] >= q) {
while (A[g] > q && k < g) --g;
swap(A, k, g);
--g;
if (A[k] < p) {
swap(A, k, l);
++l;
}
}
++k;
}
--l; ++g;

// Swap pivots to final place
swap(A, left, l); swap(A, right, g);

// Recursively sort partitions
sort(A, left, l - 1);
sort(A, l + 1, g - 1);
sort(A, g + 1, right);
}
}

void swap(int[] A, int i, int j) {
final int tmp = A[i]; A[i] = A[j]; A[j] = tmp;
}


The partitioning loop maintains the following invariant: (Initially, the “?”-area is the whole array, at the end it is gone; the indices are moved in the direction indicated by the arrays, so $\ell$ and $k$ start at the left, $g$ at the right end of $A$.)

I did a mathematical average case analysis for these algorithms to determine the expected number of key comparisons, element swaps and also instruction counts for some specific low-level implementations (in Java Bytecode and MMIX, an RISC assembly language).

The main result is that Yaroslavskiy's algorithm uses $1.9n \ln n + O(n)$ comparison, which is 5% less than the $2n \ln n + O(n)$ comparisons of classic single-pivot Quicksort (both average case on random permutations). However, it needs $0.6 n\ln n + O(n)$ swaps for that, where classic Quicksort only needs $\frac13 n \ln n + O(n)$ swaps; similarly, my instruction counts also indicate that classic Quicksort is more efficient. What exactly makes Java 7's dual-pivot algorithm faster remains an open question. (In case you are interested in more details on that, I could elaborate further.)

Tweaks of the algorithm like switching to Insertionsort for subproblems smaller than some (constant) threshold or optimizing code outside the partitioning loop (while(k <= g) { ... }) will only change the numbers hidden by $O(n)$. This means that for large lists, they are not important. For practical input sizes, they still help a lot, so having them in library code is a must.

• The actual case where dual-pivot quicksort (and the dutch national flag algorithm) does really shine is when there are duplicates in the input sequence. In other cases it is potentially slower than the classic quicksort when swaps are more expensive than comparisons (which is generally the case on modern computers). Did your analysis consider this? Feb 14, 2020 at 19:19
• Hi @plasmacel, I have worked on this a lot more in my dissertation (wild-inter.net/publications/wild-2016), trying to take many such considerations into account. Memory references seem to be much more relevant than comparisons vs swaps, but many details matter. I also looked at the question how to deal with duplicate elements. Dual-pivoting is not 'automatically' better for that. Separating out duplicates of the pivot helps a lot for these inputs, but there are many ways to do that. Feb 16, 2020 at 17:56

Check out the implementation by Joshua Bloch which is part of the jdk. It has very good documentation as well with some diagrams. If you don't want the optimization for short arrays just skip past it.

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/util/DualPivotQuicksort.java

• Please summarize the link, the page might dissappear anytime making the answer useless. Aug 28, 2015 at 0:06