The final optimized version of Dual-Pivot Quicksort (ver.19.1)

[Vladimir Yaroslavskiy]

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