Hi Vladimir, I performed lots of benchmarks:
1. I updated my own sort-bench (jmh based) and run many tests (all distributions + permutations) on integer arrays for sizes = 50, 100, 150, 200, 500, 1000, 2000: In this benchmark, the metric is (minimum + stddev) and it gives the overall score: in average, the new DPQS is 7% faster Comparing sorters DPQ_19_05_01 vs DPQ_19_08_09 winners : 349 / 321 stats (%): [1115: µ=107.99222 σ=45.746456 rms=153.73868 min=62.684937 max=524.28424] Full results are available: https://github.com/bourgesl/nearly-optimal-mergesort-code/blob/master/sort-bench/2019.08/sort-50-2000-stats.out 2. I ran Vladimir's test (from https://github.com/iaroslavski/sorting ): Before (07/24): # Data type = int, Sorting type = sequential, Length = 150 test_name;jdk_time;dpqs_time;gain random;1867.00;2074.00;-0.11 equal;224.00;98.00;0.56 ascending;476.00;112.00;0.76 descending;1185.00;260.00;0.78 period[4];564.00;782.00;-0.39 period[5];610.00;1076.00;-0.76 period[6];710.00;1028.00;-0.45 stagger[15];1788.00;2316.00;-0.30 stagger[24];709.00;1028.00;-0.45 stagger[33];2020.00;1934.00;0.04 shuffle[6];1624.00;1218.00;0.25 shuffle[7];1347.00;1189.00;0.12 shuffle[8];1345.00;1085.00;0.19 TOTAL;14469.00;14200.00;0.02 Patched (08/14): # Data type = int, Sorting type = sequential, Length = 150 test_name;jdk_time;dpqs_time;gain random;1881.00;1860.00;0.01 equal;223.00;98.00;0.56 ascending;478.00;111.00;0.77 descending;1192.00;262.00;0.78 period[4];564.00;660.00;-0.17 period[5];613.00;1014.00;-0.65 period[6];713.00;968.00;-0.36 stagger[15];1787.00;1893.00;-0.06 stagger[24];712.00;969.00;-0.36 stagger[33];2021.00;1890.00;0.06 shuffle[6];1618.00;1185.00;0.27 shuffle[7];1361.00;1129.00;0.17 shuffle[8];1341.00;1094.00;0.18 TOTAL;14504.00;13133.00;0.09 In conclusion, I confirm Vladimir's gain on my laptop (Intel(R) Core(TM) i7-6820HQ CPU @ 2.70GHz): size = 150, char, was: 0.02 -> new: 0.09 Finally both benchmarks agree 7% gain ! Cheers, Laurent