On Wed, 6 Oct 2021 21:21:29 GMT, iaroslavski <github.com+43264149+iaroslav...@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
