Re: Replacement of Quicksort in java.util.Arrays with Dual-Pivot Quicksort: improvements

2009-09-15 Thread Vladimir Yaroslavskiy
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

Re: Replacement of Quicksort in java.util.Arrays with Dual-Pivot Quicksort: improvements

2009-09-15 Thread Andrew Haley
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.

Re: Replacement of Quicksort in java.util.Arrays with Dual-Pivot Quicksort: improvements

2009-09-14 Thread Joshua Bloch
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

Re: Replacement of Quicksort in java.util.Arrays with Dual-Pivot Quicksort: improvements

2009-09-14 Thread Leonid Geller
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.

Re: Replacement of Quicksort in java.util.Arrays with Dual-Pivot Quicksort: improvements

2009-09-14 Thread Vladimir Yaroslavskiy
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