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

[Alan Bateman]

Does anyone have this on their radar to review? If not, I'll put it on 
my list.

-Alan.


Vladimir Iaroslavski wrote:
> Hello,
>
> Here is improvement for sorting primitives: 
> http://cr.openjdk.java.net/~alanb/7013585/webrev
>
> 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,
> Vladimir
>