Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort

[Vladimir Iaroslavski]

> Date: Tue, 6 Oct 2009 23:11:25 +0000 (UTC)
> From: quitos <marquits at marquits.com>
> Subject: Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
> To: core-libs-dev at openjdk.java.net
> 
> I suppose if the array is small enough, it is better to use simple Quicksort. 
> And the larger the array, the more sense it makes to use more pivots, because 
> the calculation cost of comparing against many pivots becomes more affordable 
> than iterating for a larger subset.
> So you think the optimal number of pivots to use could be directly linked to the 
> size of the array you're trying to sort?

I've tried several cases with different numbers of pivots on different length,
and experiments show that 2 pivots from 5 candidates is optimal. Note that
if you have many pivots (> 3) the loop of sorting becomes more complex and
slower. For small arrays the best choice is Insertion sort which is simpler
and faster than any quicksort.

Vladimir