It’s no news that quicksort is considered one of the most important algorithms of the century and that it is the *de facto* system sort for many languages, including the `Arrays.sort`

in Java.

**So, what’s new about quicksort? **

Well, nothing except that I just now figured out (two damn years after the release of Java 7) that the quicksort implementation of `Arrays.sort`

has been replaced with a variant called **dual-pivot quicksort**. This thread is not only awesome for this reason but also how humble Jon Bentley and Joshua Bloch really are.

### What did I do then?

Just like everybody else, I wanted to implement it and do some benchmarking against some 10 million integers (random and duplicate).

Oddly enough, I found the following results:

### Random Data

- Basic quicksort: 1222 ms
- Three-way quicksort: 1295 ms (seriously!)
- Dual-pivot quicksort: 1066 ms

### Duplicate Data

- Basic quicksort: 378 ms
- Three-way quicksort: 15 ms
- Dual-pivot quicksort: six ms

### Stupid Question One

I am afraid that I am missing something in the implementation of the three-way partition. Across several runs against random inputs (of 10 million numbers), I could see that the single pivot always performs better (although the difference is less than 100 milliseconds for 10 million numbers).

I understand that the whole purpose of making the three-way quicksort the default quicksort until now is that it does not give 0(n^{2)} performance on duplicate keys, which is very evident when I run it against duplicate inputs. But is it true that, for the sake of handling duplicate data, a small penalty is taken by the three-way quicksort? Or is my implementation bad?

### Stupid Question Two

My dual-pivot implementation (link below) does not handle duplicates well. It takes forever (0(n^{2))} to execute. Is there a good way to avoid this? Referring to the `Arrays.sort`

implementation, I figured out that ascending sequences and duplicates are eliminated well before the actual sorting is done. So, as a dirty fix, if the pivots are equal I fast-forward the *lowerIndex* until it is different than *pivot2*. Is this a fair implementation?

else if (pivot1==pivot2){ while (pivot1==pivot2 && lowIndex<highIndex){ lowIndex++; pivot1=input[lowIndex]; } }

**That’s it? That's all I did?**

I always find the tracing of the algorithm interesting, but with the number of variables in a dual-pivot quicksort, my eyes found it overwhelming while debugging. So, I also went ahead and created *trace*-enabled implementations (for all three) so that I could see where the variable pointers were in real time.

These trace-enabled classes just overlay where the pointers are below the array values. I hope you find these classes useful.

For example, for a dual-pivot iteration:

**Where can you download the code?**

The entire project (along with a few lame implementations of DSA) is available on GitHub here. The quicksort classes alone can be found here.

Here’s my implementation of the single-pivot (Hoare), three-way (Sedgewick) and the new dual-pivot (Yaroslavskiy)

**Single Pivot**

package basics.sorting.quick; import static basics.sorting.utils.SortUtils.exchange; import static basics.sorting.utils.SortUtils.less; import basics.shuffle.KnuthShuffle; public class QuickSortBasic { public void sort (int[] input){ //KnuthShuffle.shuffle(input); sort (input, 0, input.length-1); } private void sort(int[] input, int lowIndex, int highIndex) { if (highIndex<=lowIndex){ return; } int partIndex=partition (input, lowIndex, highIndex); sort (input, lowIndex, partIndex-1); sort (input, partIndex+1, highIndex); } private int partition(int[] input, int lowIndex, int highIndex) { int i=lowIndex; int pivotIndex=lowIndex; int j=highIndex+1; while (true){ while (less(input[++i], input[pivotIndex])){ if (i==highIndex) break; } while (less (input[pivotIndex], input[--j])){ if (j==lowIndex) break; } if (i>=j) break; exchange(input, i, j); } exchange(input, pivotIndex, j); return j; } }

**Three-way**

package basics.sorting.quick; import static basics.shuffle.KnuthShuffle.shuffle; import static basics.sorting.utils.SortUtils.exchange; import static basics.sorting.utils.SortUtils.less; public class QuickSort3Way { public void sort (int[] input){ //input=shuffle(input); sort (input, 0, input.length-1); } public void sort(int[] input, int lowIndex, int highIndex) { if (highIndex<=lowIndex) return; int lt=lowIndex; int gt=highIndex; int i=lowIndex+1; int pivotIndex=lowIndex; int pivotValue=input[pivotIndex]; while (i<=gt){ if (less(input[i],pivotValue)){ exchange(input, i++, lt++); } else if (less (pivotValue, input[i])){ exchange(input, i, gt--); } else{ i++; } } sort (input, lowIndex, lt-1); sort (input, gt+1, highIndex); } }

**Dual-pivot**

package basics.sorting.quick; import static basics.shuffle.KnuthShuffle.shuffle; import static basics.sorting.utils.SortUtils.exchange; import static basics.sorting.utils.SortUtils.less; public class QuickSortDualPivot { public void sort (int[] input){ //input=shuffle(input); sort (input, 0, input.length-1); } private void sort(int[] input, int lowIndex, int highIndex) { if (highIndex<=lowIndex) return; int pivot1=input[lowIndex]; int pivot2=input[highIndex]; if (pivot1>pivot2){ exchange(input, lowIndex, highIndex); pivot1=input[lowIndex]; pivot2=input[highIndex]; //sort(input, lowIndex, highIndex); } else if (pivot1==pivot2){ while (pivot1==pivot2 && lowIndex<highIndex){ lowIndex++; pivot1=input[lowIndex]; } } int i=lowIndex+1; int lt=lowIndex+1; int gt=highIndex-1; while (i<=gt){ if (less(input[i], pivot1)){ exchange(input, i++, lt++); } else if (less(pivot2, input[i])){ exchange(input, i, gt--); } else{ i++; } } exchange(input, lowIndex, --lt); exchange(input, highIndex, ++gt); sort(input, lowIndex, lt-1); sort (input, lt+1, gt-1); sort(input, gt+1, highIndex); } }

## Comments

## Pablo Garin replied on Wed, 2013/08/14 - 7:34am

Hi!, very interesting implementation, and good results too!

## Sada Kurapati replied on Wed, 2013/09/11 - 6:57pm

Nice explanation and the running time sampling numbers are always good. Thank You very much for this article Arun!!

## Andre Bogus replied on Thu, 2014/02/06 - 3:08am

Your dual-pivot quicksort contains an error. You increase lowIndex in line 30, ensuring that everything before it is never sorted. Try to sort [7, 6, 7, 7, 7] to see what I mean.