Dual-Pivot Quicksort and Sorting classes: update

[Vladimir Iaroslavski]

Hello,

Here is next update of Quicksort and Sorting classes, summary of changes:

1. Threshold for insertion sort was increased from 32 to 47.

2. Approximation of length/7 uses >> shift instead of >>> now
    (we know that length > threshold > 0)

int seventh = (length >> 3) + (length >> 6) + 1;

3. Method sort(byte[]) (and sort(byte[],int,int) uses
insertion sort for small array (<= 29) and counting sort for other
(no quicksort at all).

4. Improved message outputs in Sorting class.

Thank you,
Vladimir

Vladimir Iaroslavski wrote:
> Hello!
> 
> I updated Dual-Pivot Quicksort and Sorting classes.
> 
> http://cr.openjdk.java.net/~alanb/6976036/webrev
> 
> In compare with previous version the ratio (JDK 7 / JDK 6)
> now is (client / server): 54.35% / 42.79% (was 57.22% / 46.18%).
> 
> Summary of changes:
> 
> Sorting class: new type of test (check sum with plus operation) was added.
> Dual-Pivot Quicksort:
> 
> 1. Changes in for-loop from
> 
> for (int i = <lo> + 1; i < <hi>; i++)
> 
> to
> 
> for (int i = <lo>; ++i < <hi>; )
> 
> 2. Skip the longest ascending sequence in insertion sort:
> 
> while (left <= right && a[left - 1] <= a[left]) {
>     left++;
> }
> 
> 3. Added comment about a[i]; i++; issue.
> 
> 4. Corrected comment with value when sqan of equal to
> pivots is started: 5/7 -> 4/7.
> 
> 5. Other minor javadoc changes.
> 
> Please review the changes.
> 
> Thank you,
> Vladimir
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: DualPivotQuicksort.java
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20100901/e1923472/DualPivotQuicksort.java>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: Sorting.java
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20100901/e1923472/Sorting.java>