One quick comment: you can consider moving trivial array check so it will be executed only if insertion sort threshold check passes:<div><span class="Apple-style-span" style="font-family: Times; font-size: medium; "><pre><span class="new" style="color: blue; font-weight: normal; ">if (length < INSERTION_SORT_THRESHOLD) {
  if (length < 2) {
    return;
  }
  ....</span></pre></span></div><div><br><br><div class="gmail_quote">On Mon, Apr 26, 2010 at 2:50 PM, Vladimir Iaroslavski <span dir="ltr"><<a href="mailto:vladimir.iaroslavski@googlemail.com">vladimir.iaroslavski@googlemail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Hello, everyone!<br>
<br>
I've investigated the implementation of the Dual-Pivot Quicksort<br>
which is used for sorting primitives and here is my result:<br>
<br>
<a href="http://cr.openjdk.java.net/~alanb/6947216/webrev.00" target="_blank">http://cr.openjdk.java.net/~alanb/6947216/webrev.00</a><br>
<br>
New implementation of Dual-Pivot Quicksort is faster<br>
than previous one of 12% for client VM and few percents for<br>
server VM. Tests on Bentley's test suite (Win XP, JDK 7,<br>
build 1.7.0-ea-b84, n = 1000000) show geometry mean 0.88<br>
for client VM and 0.98-1.00 for server VM.<br>
<br>
In compare with sorting from JDK 6 by Jon L. Bentley and<br>
M. Douglas McIlroy's (with one pivot) the ratio is 0.61 / 0.50<br>
(client / server).<br>
<br>
See the execution time for sorting array of 2`000`000 int elements<br>
50 times, client / server VM, in milliseconds:<br>
<br>
random<br>
 new: 16723 18776<br>
jdk7: 17571 18975<br>
jdk6: 22241 26524<br>
<br>
ascendant<br>
 new:  3541  4702<br>
jdk7:  4486  4669<br>
jdk6:  8667  7978<br>
<br>
descendant<br>
 new:  3854  4907<br>
jdk7:  4942  5034<br>
jdk6:  8787  8243<br>
<br>
equal<br>
 new:   234   281<br>
jdk7:   291   230<br>
jdk6:   602  1018<br>
<br>
organ pipes<br>
 new:  7673  8613<br>
jdk7:  8167  8993<br>
jdk6: 11902 14044<br>
<br>
stagger 1<br>
 new:  7648  8591<br>
jdk7:  8161  8979<br>
jdk6: 11908 13810<br>
<br>
stagger 2<br>
 new:  8349  9299<br>
jdk7: 10968 11916<br>
jdk6: 12194 14734<br>
<br>
stagger 4<br>
 new:  8475  9622<br>
jdk7:  9221  9682<br>
jdk6: 10523 12006<br>
<br>
stagger 8<br>
 new:  9321 10689<br>
jdk7: 11125 12387<br>
jdk6: 13829 16214<br>
<br>
period 1..2<br>
 new:   758   751<br>
jdk7:   870   754<br>
jdk6:  1038  1227<br>
<br>
period 1..4<br>
 new:  1004   963<br>
jdk7:  1365  1209<br>
jdk6:  1511  1847<br>
<br>
period 1..8<br>
 new:  1588  1573<br>
jdk7:  1599  1790<br>
jdk6:  2602  3045<br>
<br>
random 1..2<br>
 new:  1327  1125<br>
jdk7:  1362  1496<br>
jdk6:  1531  2182<br>
<br>
random 1..4<br>
 new:  1830  2118<br>
jdk7:  1851  2236<br>
jdk6:  2292  3025<br>
<br>
where stagger(m) is array like a[i] = i * (m + 1) % length.<br>
<br>
The summary of changes is:<br>
<br>
1. For sorting small arrays is used insertion sort with sentinel<br>
instead of traditional, which has the structure:<br>
<br>
for (int i = left + 1; i <= right; i++) {<br>
    for (j = i; j > left && a[j-1] > a[j]; j--) {<br>
        swap(a[i], a[j-1]);<br>
    }<br>
}<br>
<br>
Note that range check j > left is performed on each iteration,<br>
but really helps very rare. To avoid this expensive range check,<br>
it was suggested to set minimum value (negative infinity) on the<br>
first position. This type of suggestion is used in new version:<br>
<br>
if left bound > 0, we can put sentinel on a[left - 1], do insertion<br>
sort without expensive check range, and then restore a[left - 1]<br>
value. If left == 0, traditional insertion sort is used. Please,<br>
look at the webrev for details.<br>
<br>
2. In previous implementation 5 evenly spaced elements<br>
<br>
sixth = length / 6;<br>
a[sixth], a[2 * sixth], a[3 * sixth], a[4 * sixth], a[5 * sixth]<br>
<br>
were used as candidates of pivots elements. This case is very<br>
sensitive for period inputs, especially by 6. The new suggestion<br>
is to take 5 center evenly spaced elements like this:<br>
<br>
int seventh = length / 7;<br>
int midpoint = (left + right) >>> 1;<br>
<br>
a[midpoint - 2 * seventh], a[midpoint -     seventh], a[midpoint],<br>
a[midpoint +     seventh], a[midpoint + 2 * seventh]<br>
<br>
and moreover, the seventh is calculated inexpensively:<br>
seventh = (length >>> 3) + (length >>> 6) + 1;<br>
<br>
This schema works the same on random, ascendant, descendant, equal<br>
inputs, but much better for period / stagger.<br>
<br>
3. The whole structure<br>
<br>
<choose pivots><br>
<br>
if (pivotsDiffer) {<br>
    <do partitioning for two pivots><br>
}<br>
else {<br>
    <do partitioning for one pivot><br>
}<br>
<br>
<sort left and right parts><br>
<br>
if (!pivotsDiffer) {<br>
    return;<br>
}<br>
<swap internal pivot values to ends><br>
<br>
<sort center part><br>
<br>
was modified to:<br>
----------------<br>
<br>
<choose pivots><br>
<br>
if (pivot1 < pivot2) {<br>
    <do partitioning for two pivots><br>
    <swap pivots into their final positions><br>
    <sort left and right parts><br>
    <swap internal pivot values to ends><br>
    <sort center part><br>
}<br>
else {<br>
    <do partitioning for one pivot><br>
    <sort left and right parts><br>
}<br>
<br>
4. Partitioning for both cases have not been changed at all.<br>
<br>
5. Minor javadoc and format changes.<br>
<br>
Please, review new implementation,<br>
any comments / suggestions are welcome!<br>
<br>
Thank you,<br>
<font color="#888888">Vladimir<br>
</font></blockquote></div><br></div>