Dual Pivot Quicksort in Java

This is from the paper published by Vladimir Yaroslavskiy (Read it for more details : here

Sorting data is one of the most fundamental problems in Computer Science, especially if the arranging objects are primitive ones, such as integers, bytes, floats, etc. Since sorting methods play an important role in the operation of computers and other data processing systems, there has been an interest in seeking new algorithms better than the existing ones. We compare sorting methods by the number of the most "expensive" operations, which influence on effectiveness of the sorting techniques, — comparisons and swaps. Quicksort algorithm is an effective and wide-spread sorting procedure with C*n *ln(n) operations, where n is the size of the arranged array. The problem is to find an algorithm with the least coefficient C. There were many attempts to improve the classical variant of the Quicksort algorithm:

1. Pick an element, called a pivot, from the array.
2. Reorder the array so that all elements, which are less than the pivot, come before the pivot and all elements greater than the pivot come after it (equal values can go
either way). After this partitioning, the pivot element is in its final position.
3. Recursively sort the sub-array of lesser elements and the sub-array of greater elements.

We can show that using two pivot elements (or partitioning to three parts) is
more effective, especially on large arrays. We suggest the new Dual-Pivot Quicksort
scheme, faster than the known implementations, which improves this situation. The
implementation of the Dual-Pivot Quicksort algorithm has been investigated on different inputs and primitive data types. Its advantages in comparison with one of the most effective known implementations of the classical Quicksort algorithm [1], [2], and implementation of Quicksort in JDK™ 6.0 platform [3] have been shown.

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively.



Here is the source code for the implementation : Code by Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch.


Comparision between Current JDK Quicksort vs Dual Pivot Quick sort : comparision