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
One thing that occurred to me, and I'm sorry if this question has been
asked already but I couldn't find it:
TINY_SIZE, the threshold for insertion sorting, has gone up from 7 to 17.
Does this mean that sorting arrays of this size is now slower?
Andrew.
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 i
Remarkable performance improvements!
The next step to make this "jdk" material is to implement the DPQ using
collections and generics. Then offer an API to pass a comparator class or insure
the sortable data structure implements comparable interface.
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 el