Hi team, Please review the final optimized version of Dual-Pivot Quicksort (ver.19.1), see http://cr.openjdk.java.net/~alanb/8226297/0/webrev (link to Jira task https://bugs.openjdk.java.net/browse/JDK-8226297)
The new version was published here more than one year ago (on Jan 19, 2018). Since that time Dual-Pivot Quicksort has been significantly improved and this work was done in collaboration with Doug Lea and Laurent Bourges. You can find summary of all changes below. DualPivotQuicksort.java ---------------------------------------------------------------------- * The 1-st and 5-th candidates are taken as pivots instead of 2-nd and 4-th * Pivots are chosen with another step * Pivot candidates are sorted by combination of 5-element network sorting and insertion sort * New backwards partitioning was introduced * Partitioning is related to the golden ratio * Quicksort tuning parameters were updated * Thresholds for byte / char / short sorting were updated * Additional steps for float / double were fully rewritten * Parallel sorting is based on combination of merge sort and Dual-Pivot Quicksort * Pair insertion sort was optimized and became a part of mixed insertion sort * Mixed insertion sort was introduced: combination of simple insertion sort, pin insertion sort and pair insertion sort * Simple insertion sort is invoked on tiny array * Pin insertion sort is started on small array * Pair insertion sort is continued on remain part * Merging of runs is invoked on each iteration of Quicksort * Merging of runs was fully rewritten * Optimal partitioning of merging is used * Not more than one copy of part to buffer during merging * Merging parameters were updated * Initial capacity of runs is based on size * Max number of runs is constant * Optimized version of heap sort was introduced * Heap sort is used as a guard against quadratic time (int / long / float / double) * Parallel merging of runs was also provided * Parallel sorting, heap sort and merging of runs are not used in byte / char / short sorting * Counting sort for byte / char / short were optimized * Counting sort is used as a guard against quadratic time (byte / char / short) * Code style and javadoc improvements Sorting.java ---------------------------------------------------------------------- * New test cases were added * Test cases are invoked for both: sequential and parallel sorting * Check for Object sorting was added * New tests were added against heap sort * Added test case against bug in parallel merge sort on float / double data ParallelSorting.java ---------------------------------------------------------------------- * This class was removed, because Sorting class covers all cases SortingHelper.java ---------------------------------------------------------------------- * The helper class provides access package-private methods of DualPivotQuicksort class during testing Arrays.java ---------------------------------------------------------------------- * Calls of Dual-Pivot Quicksort were updated * Parallel sorting of primitives was switched to parallel Dual-Pivot Quicksort * Javadoc was updated, double spaces were removed * Format changes ArraysParallelSortHelpers.java ---------------------------------------------------------------------- * Implementation of parallel sorting for primitives was removed * Javadoc was updated Thank you, Vladimir