Date: Tue, 6 Oct 2009 23:11:25 +0000 (UTC)
From: quitos <marqu...@marquits.com>
Subject: Re: Replacement of Quicksort in java.util.Arrays with new Dual-Pivot
Quicksort
To: core-libs-dev@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
