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

[Vladimir Iaroslavski]

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