Hi, I’d like to share new improvement of Dual-Pivot Quicksort: new algorithm of sorting, Radix sort, is suggested. Also performance was improved in case of corner merging of runs. The changes are: 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 See related JDB and PR https://bugs.openjdk.java.net/browse/JDK-8266431 https://github.com/openjdk/jdk/pull/3938 Laurent Bourges has tested new version of Dual-Pivot Quicksort, it shows better performance. --- STATS --- Comparing sorters SYSTEM vs NEW_DPQS_REF winners : 75 / 197 avg (%): 125.5317 stats (%): [360: µ=146.05562 σ=106.212036 rms=252.26765 min=29.021154 max=618.46735] Stats per keys: IDENT_____:SPIRAL stats (%): [12: µ=146.85367 σ=67.929474 rms=214.78313 min=81.47126 max=301.9469] IDENT_____:STAGGER stats (%): [12: µ=124.82189 σ=85.498825 rms=210.32072 min=81.963005 max=395.48715] IDENT_____:SAWTOTH stats (%): [12: µ=121.015236 σ=48.471672 rms=169.48691 min=92.21825 max=227.12547] IDENT_____:_RANDOM stats (%): [12: µ=235.53735 σ=204.9386 rms=440.47595 min=84.627625 max=613.981] IDENT_____:PLATEAU stats (%): [12: µ=99.05677 σ=1.7938316 rms=100.85061 min=95.937035 max=100.65806] IDENT_____:SHUFFLE stats (%): [12: µ=91.41511 σ=19.296474 rms=110.71158 min=57.53845 max=117.839775] REVERSE___:SPIRAL stats (%): [12: µ=214.24744 σ=86.17577 rms=300.42322 min=90.77709 max=355.51056] REVERSE___:STAGGER stats (%): [12: µ=127.6578 σ=87.32062 rms=214.97841 min=94.24164 max=404.43817] REVERSE___:SAWTOTH stats (%): [12: µ=121.37123 σ=39.691704 rms=161.06294 min=95.34109 max=209.51929] REVERSE___:_RANDOM stats (%): [12: µ=251.44595 σ=221.17654 rms=472.6225 min=86.738144 max=618.46735] REVERSE___:PLATEAU stats (%): [12: µ=104.74188 σ=6.7017303 rms=111.44361 min=97.345634 max=120.3795] REVERSE___:SHUFFLE stats (%): [12: µ=100.18308 σ=19.42561 rms=119.608696 min=69.78542 max=135.48901] DITHER____:SPIRAL stats (%): [12: µ=183.42812 σ=64.67034 rms=248.09845 min=99.713776 max=268.3382] DITHER____:STAGGER stats (%): [12: µ=174.41586 σ=123.18825 rms=297.60413 min=99.123314 max=459.56564] DITHER____:SAWTOTH stats (%): [12: µ=187.5975 σ=110.62237 rms=298.21988 min=97.2715 max=367.14056] DITHER____:_RANDOM stats (%): [12: µ=185.65709 σ=129.0605 rms=314.7176 min=70.168724 max=434.8079] DITHER____:PLATEAU stats (%): [12: µ=100.72014 σ=3.9355173 rms=104.655655 min=94.559074 max=107.78911] DITHER____:SHUFFLE stats (%): [12: µ=86.45017 σ=42.46921 rms=128.91939 min=29.021154 max=171.31981] REVERSE_BA:SPIRAL stats (%): [12: µ=177.85292 σ=85.1786 rms=263.03152 min=94.477264 max=315.87576] REVERSE_BA:STAGGER stats (%): [12: µ=132.4794 σ=103.280464 rms=235.75987 min=97.76542 max=460.07227] REVERSE_BA:SAWTOTH stats (%): [12: µ=110.42876 σ=23.894398 rms=134.32315 min=98.04496 max=182.87247] REVERSE_BA:_RANDOM stats (%): [12: µ=223.70018 σ=185.21355 rms=408.91373 min=86.62554 max=618.0156] REVERSE_BA:PLATEAU stats (%): [12: µ=99.096275 σ=1.8192571 rms=100.91553 min=95.90717 max=100.805466] REVERSE_BA:SHUFFLE stats (%): [12: µ=101.3669 σ=22.24021 rms=123.60711 min=65.73001 max=144.21266] REVERSE_FR:SPIRAL stats (%): [12: µ=190.94035 σ=74.251236 rms=265.1916 min=97.7578 max=358.39563] REVERSE_FR:STAGGER stats (%): [12: µ=134.06009 σ=104.719696 rms=238.77979 min=98.797386 max=466.2626] REVERSE_FR:SAWTOTH stats (%): [12: µ=110.6682 σ=27.3231 rms=137.9913 min=94.27639 max=195.0114] REVERSE_FR:_RANDOM stats (%): [12: µ=248.0682 σ=201.4303 rms=449.4985 min=97.789764 max=614.1303] REVERSE_FR:PLATEAU stats (%): [12: µ=99.416336 σ=7.2677627 rms=106.6841 min=87.80682 max=115.78382] REVERSE_FR:SHUFFLE stats (%): [12: µ=96.97448 σ=18.399363 rms=115.37385 min=64.20668 max=130.8938] https://github.com/bourgesl/nearly-optimal-mergesort-code/tree/master/sort-bench/results/2021/2105-final Radix Sort benchmark https://github.com/bourgesl/radix-sort-benchmark/blob/main/results/2021-ref/cmp-16-1M-global-final-2.log Thank you, Vladimir
