Hello Andrew,
It means that the threshold = 7 is optimal for combination:
insertion sort + Bentley's implementation, and
17 - for Insertion + Dual-Pivot Quicksort.
I can add that for Dual-Pivot Quicksort old threshold = 7
shows slower results than 17.
Other values, such as 25, 27, show similar
Hi Team,
Thank you very much for your feedback and comments!
I collect here all hints and tips for improvement of
the new algorithm. New version of Quicksort is attached.
And now my investigations:
1. [Jon Bentley]
Use the median of 2k+1 elements for pivots.
We can choose a sample of five
Leonid,
I don't think Dual Pivot Quicksort for List is necessary or appropriate.
Recall that Arrays.sort and Collections.sort are defined to be stable
sorts, which Quicksort is not. Also, I just replaced them with TimSort,
which gives a very healthy performance boost.
I do think it would be an
