1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Wandering Logic Apr 25 '14 at 1:13
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Apr 25 '14 at 6:57
  • $\begingroup$ @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. $\endgroup$ – Raphael Apr 25 '14 at 6:59
  • $\begingroup$ @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. $\endgroup$ – 500 - Internal Server Error Apr 25 '14 at 8:29
  • $\begingroup$ @500-InternalServerError It's important to say that; there have been other multi-pivot Quicksorts decades ago which are slightly (but significantly) different. $\endgroup$ – Raphael Apr 25 '14 at 8:31
8
$\begingroup$

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: partitioning invariant of Yaroslavskiy's algorithm (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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Please summarize the link, the page might dissappear anytime making the answer useless. $\endgroup$ – vonbrand Aug 28 '15 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.