Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
iaroslavski at mail.ru
Mon Oct 19 06:18:16 PDT 2009
> 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.
More information about the core-libs-dev