The new optimized version of Dual-Pivot Quicksort

Vladimir Yaroslavskiy at
Fri Jan 19 13:38:03 UTC 2018

Hi team,

In Sept 2009 Josh Bloch, Jon Bentley and I introduced new sorting
algorithm, Dual-Pivot Quicksort, for primitives in JDK 7 and later
I suggested several improvements of Dual-Pivot Quicksort, which
were integrated into JDK 8.

Now I have more optimized and faster version of Dual-Pivot Quicksort.
I have been working on it for the last 5 years. Please, find the
summary of changes below and sources / diff at webrev [1].

All tests and benchmarking were run on the most recent build of JDK 10,
jdk-10-ea+39. The new version shows the better performance on different
inputs and guarantees n*log(n) on any data.

The new implementation of Dual-Pivot Quicksort is 'all-in-one' version:
it contains one code for both parallel and sequential sorting algorithms.

Suggested version is 10-20% faster on random data, 1.5-4 times faster
on nearly structured arrays, 1.5-2 times faster on period inputs.

Parallel Dual-Pivot Quicksort is 1.5-3 times faster than current
algorithm based on merge sort.

Benchmarking on the test suite, suggested by Jon Bentley, shows the
boost of performance in 1.4 times. This test suite contains several
types of inputs, such as random data, nearly structured arrays, data
with period and so on. Also there are several modifications of inputs
and parameters which are used in data building. We run sorting on all
combinations to compare two algorithms.

Please let me know if you have any questions / comments.

Summary of changes:

DualPivotQuicksort class
* Pivots are chosen with another step, the 1-st and 5-th candidates
   are taken as pivots instead of 2-nd and 4-th.
* Splitting into parts is related to the golden ratio
* Pivot candidates are sorted by combination of 5-element
   network sorting + insertion sort
* New backwards partitioning is simpler and more efficient
* Quicksort tuning parameters were updated
* Merging sort is invoked on each iteration from Quicksort
* Additional steps for float/double were fully rewritten
* Heap sort is invoked on the leftmost part
* Heap sort is used as a guard against quadratic time
* Parallel sorting is based on Dual-Pivot Quicksort
   instead of merge sort

SortingAlgorithms class
* Merging sort and pair insertion sort were moved from
   DualPivotQuicksort class
* Pair insertion sort was simplified and optimized
* New nano insertion sort was introduced for tiny arrays
* Merging sort was fully rewritten
* Optimized merging partitioning is used
* Merging parameters were updated
* Merging of runs was fully rewritten
* Fast version of heap sort was introduced
* Parallel merging sort was also provided

Sorting / ParallelSorting classes
* New test cases were added
* Sources of these classes were unified

Arrays class
* Calls of Dual-Pivot Quicksort were updated
* Parallel sorting of primitives was switched to parallel
   Dual-Pivot Quicksort
* Javadoc was modified

ArraysParallelSortHelpers class
* Old implementation of parallel sorting for primitives was removed
* Javadoc was updated

Thank you,


More information about the core-libs-dev mailing list