Dual-Pivot Quicksort improvements for highly structured (nearly sorted) arrays and data with small periods
Alan.Bateman at oracle.com
Fri Jan 28 09:57:31 UTC 2011
Does anyone have this on their radar to review? If not, I'll put it on
Vladimir Iaroslavski wrote:
> Here is improvement for sorting primitives:
> Highly structured (nearly sorted) data like
> 1,2,3,..,k,1,2,3,..,k,... or
> 1,2,3,...,n/2,n/2,...,3,2,1 etc.
> is sorted very effectively by merge sort.
> The main idea of this optimization is to check
> if given array is nearly sorted and apply modified
> and improved merge sort on it. Otherwise, Dual-Pivot
> Quicksort is applied.
> Note that the check doesn't decrease the performance of sorting.
> Other optimization is related to random or repeated data
> with small period, m <= 10. This type of data is sorted
> faster by Quicksort with one pivot but with DNF (Dutch
> National Flag) partition. Therefore, sorting is switched
> to DNF even calculated pivots are different.
> The boost of performance with new optimizations is:
> random data: new: 135, old: 154, ratio: 87.6%
> ascending: new: 3, old: 45, ratio: 6.6%
> descending: new: 5, old: 48, ratio: 10.4%
> organ pipes: new: 20, old: 80, ratio: 25%
> period(m), m <= 10: new: 10, old: 15, ratio: 66.6%
> random(m), m <= 10: new: 11, old: 16, ratio: 68.7%
> equal: new: 2.5, old: 3, new: 83.3%
> On test suite suggested by Jon Bentley we see
> the following performance:
> client VM: old 56%, new 43%
> server VM: old 46%, new 29%
> Thank you,
More information about the core-libs-dev