Dual-Pivot Quicksort improvements for highly structured (nearly sorted) arrays and data with small periods

Vladimir Iaroslavski iaroslavski at mail.ru
Thu Jan 20 18:09:19 UTC 2011


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 mailing list