RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v6]

[iaroslavski]

On Wed, 6 Oct 2021 21:21:29 GMT, iaroslavski <github.com+43264149+iaroslavski at openjdk.org> wrote:

>> Sorting:
>> 
>> - adopt radix sort for sequential and parallel sorts on int/long/float/double arrays (almost random and length > 6K)
>> - fix tryMergeRuns() to better handle case when the last run is a single element
>> - minor javadoc and comment changes
>> 
>> Testing:
>> - add new data inputs in tests for sorting
>> - add min/max/infinity values to float/double testing
>> - add tests for radix sort
>
> iaroslavski has updated the pull request incrementally with one additional commit since the last revision:
> 
>   JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
>   
>   Added more comments

LSD (Least Significant Digit) Radix sort is introduced to improve sorting.
Thшs algorithm requires additional buffer, but has O(n) complexity. At the
same time Quicksort performs at O(n*ln(n)). Radix sort shows extremely better
performance on large random data, whereas Quicksort or merging sort win
on other inputs.
 
We reuse additional buffer, if it is created during merge sort (in case of
parallel sorting on computer with many processors). The same approach is used
during allocation of buffer in merging sort. So, additional buffer is not
created twice.
 
We also check if we have enough memory for the buffer. Otherwise,
sorting is continued with in-place algorithms only.
 
Summary: introduced Radix sort requires the same amount memory
as merge or merging sorts, reuses it if necessary, but works much
faster than Quicksort.

-------------

PR: https://git.openjdk.java.net/jdk/pull/3938