changeset 2573:a5a34c696d62

6947216: Even more Dual-pivot quicksort improvements Reviewed-by: jjb Contributed-by: vladimir.yaroslavskiy@sun.com
author alanb
date Thu, 01 Jul 2010 16:28:08 +0100
parents ce0ba8da0bd1
children c0d2a097eb99
files src/share/classes/java/util/DualPivotQuicksort.java test/java/util/Arrays/Sorting.java
diffstat 2 files changed, 2200 insertions(+), 1421 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/DualPivotQuicksort.java	Wed Jun 30 16:11:32 2010 -0700
+++ b/src/share/classes/java/util/DualPivotQuicksort.java	Thu Jul 01 16:28:08 2010 +0100
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2009, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -27,7 +27,7 @@
 
 /**
  * This class implements the Dual-Pivot Quicksort algorithm by
- * Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. The algorithm
+ * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm
  * offers O(n log(n)) performance on many data sets that cause other
  * quicksorts to degrade to quadratic performance, and is typically
  * faster than traditional (one-pivot) Quicksort implementations.
@@ -36,7 +36,8 @@
  * @author Jon Bentley
  * @author Josh Bloch
  *
- * @version 2009.11.29 m765.827.12i
+ * @version 2010.06.21 m765.827.12i:5\7
+ * @since 1.7
  */
 final class DualPivotQuicksort {
 
@@ -68,7 +69,7 @@
     private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 32768;
 
     /*
-     * Sorting methods for 7 primitive types.
+     * Sorting methods for seven primitive types.
      */
 
     /**
@@ -77,7 +78,7 @@
      * @param a the array to be sorted
      */
     public static void sort(int[] a) {
-        doSort(a, 0, a.length - 1);
+        sort(a, 0, a.length - 1, true);
     }
 
     /**
@@ -95,98 +96,132 @@
      */
     public static void sort(int[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        doSort(a, fromIndex, toIndex - 1);
+        sort(a, fromIndex, toIndex - 1, true);
     }
 
     /**
-     * Sorts the specified range of the array into ascending order. This
-     * method differs from the public {@code sort} method in that the
-     * {@code right} index is inclusive, and it does no range checking
-     * on {@code left} or {@code right}.
+     * Sorts the specified range of the array into ascending order by the
+     * Dual-Pivot Quicksort algorithm. This method differs from the public
+     * {@code sort} method in that the {@code right} index is inclusive,
+     * it does no range checking on {@code left} or {@code right}, and has
+     * boolean flag whether insertion sort with sentinel is used or not.
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param leftmost indicates if the part is the most left in the range
      */
-    private static void doSort(int[] a, int left, int right) {
+    private static void sort(int[] a, int left, int right, boolean leftmost) {
+        int length = right - left + 1;
+
         // Use insertion sort on tiny arrays
-        if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
-            for (int i = left + 1; i <= right; i++) {
-                int ai = a[i];
-                int j;
-                for (j = i - 1; j >= left && ai < a[j]; j--) {
-                    a[j + 1] = a[j];
+        if (length < INSERTION_SORT_THRESHOLD) {
+            if (!leftmost) {
+                /*
+                 * Every element in adjoining part plays the role
+                 * of sentinel, therefore this allows us to avoid
+                 * the j >= left check on each iteration.
+                 */
+                for (int j, i = left + 1; i <= right; i++) {
+                    int ai = a[i];
+                    for (j = i - 1; ai < a[j]; j--) {
+                        // assert j >= left;
+                        a[j + 1] = a[j];
+                    }
+                    a[j + 1] = ai;
                 }
-                a[j + 1] = ai;
+            } else {
+                /*
+                 * For case of leftmost part traditional (without a sentinel)
+                 * insertion sort, optimized for server JVM, is used.
+                 */
+                for (int i = left, j = i; i < right; j = ++i) {
+                    int ai = a[i + 1];
+                    while (ai < a[j]) {
+                        a[j + 1] = a[j];
+                        if (j-- == left) {
+                            break;
+                        }
+                    }
+                    a[j + 1] = ai;
+                }
             }
-        } else { // Use Dual-Pivot Quicksort on large arrays
-            dualPivotQuicksort(a, left, right);
+            return;
         }
-    }
 
-    /**
-     * Sorts the specified range of the array into ascending order by the
-     * Dual-Pivot Quicksort algorithm.
-     *
-     * @param a the array to be sorted
-     * @param left the index of the first element, inclusive, to be sorted
-     * @param right the index of the last element, inclusive, to be sorted
-     */
-    private static void dualPivotQuicksort(int[] a, int left, int right) {
-        // Compute indices of five evenly spaced elements
-        int sixth = (right - left + 1) / 6;
-        int e1 = left  + sixth;
-        int e5 = right - sixth;
+        // Inexpensive approximation of length / 7
+        int seventh = (length >>> 3) + (length >>> 6) + 1;
+
+        /*
+         * Sort five evenly spaced elements around (and including) the
+         * center element in the range. These elements will be used for
+         * pivot selection as described below. The choice for spacing
+         * these elements was empirically determined to work well on
+         * a wide variety of inputs.
+         */
         int e3 = (left + right) >>> 1; // The midpoint
-        int e4 = e3 + sixth;
-        int e2 = e3 - sixth;
+        int e2 = e3 - seventh;
+        int e1 = e2 - seventh;
+        int e4 = e3 + seventh;
+        int e5 = e4 + seventh;
 
-        // Sort these elements using a 5-element sorting network
-        int ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+        // Sort these elements using insertion sort
+        if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
 
-        if (ae1 > ae2) { int t = ae1; ae1 = ae2; ae2 = t; }
-        if (ae4 > ae5) { int t = ae4; ae4 = ae5; ae5 = t; }
-        if (ae1 > ae3) { int t = ae1; ae1 = ae3; ae3 = t; }
-        if (ae2 > ae3) { int t = ae2; ae2 = ae3; ae3 = t; }
-        if (ae1 > ae4) { int t = ae1; ae1 = ae4; ae4 = t; }
-        if (ae3 > ae4) { int t = ae3; ae3 = ae4; ae4 = t; }
-        if (ae2 > ae5) { int t = ae2; ae2 = ae5; ae5 = t; }
-        if (ae2 > ae3) { int t = ae2; ae2 = ae3; ae3 = t; }
-        if (ae4 > ae5) { int t = ae4; ae4 = ae5; ae5 = t; }
-
-        a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+        if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
+            if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+        }
+        if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
+            if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+                if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+            }
+        }
+        if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
+            if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
+                if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+                    if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+                }
+            }
+        }
 
         /*
          * Use the second and fourth of the five sorted elements as pivots.
          * These values are inexpensive approximations of the first and
          * second terciles of the array. Note that pivot1 <= pivot2.
-         *
-         * The pivots are stored in local variables, and the first and
-         * the last of the elements to be sorted are moved to the locations
-         * formerly occupied by the pivots. When partitioning is complete,
-         * the pivots are swapped back into their final positions, and
-         * excluded from subsequent sorting.
          */
-        int pivot1 = ae2; a[e2] = a[left];
-        int pivot2 = ae4; a[e4] = a[right];
+        int pivot1 = a[e2];
+        int pivot2 = a[e4];
 
         // Pointers
-        int less  = left  + 1; // The index of first element of center part
-        int great = right - 1; // The index before first element of right part
+        int less  = left;  // The index of the first element of center part
+        int great = right; // The index before the first element of right part
 
-        boolean pivotsDiffer = (pivot1 != pivot2);
+        if (pivot1 != pivot2) {
+            /*
+             * The first and the last elements to be sorted are moved to the
+             * locations formerly occupied by the pivots. When partitioning
+             * is complete, the pivots are swapped back into their final
+             * positions, and excluded from subsequent sorting.
+             */
+            a[e2] = a[left];
+            a[e4] = a[right];
 
-        if (pivotsDiffer) {
+            /*
+             * Skip elements, which are less or greater than pivot values.
+             */
+            while (a[++less] < pivot1);
+            while (a[--great] > pivot2);
+
             /*
              * Partitioning:
              *
-             *   left part         center part                    right part
-             * +------------------------------------------------------------+
-             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
-             * +------------------------------------------------------------+
-             *              ^                          ^       ^
-             *              |                          |       |
-             *             less                        k     great
+             *   left part           center part                   right part
+             * +--------------------------------------------------------------+
+             * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
+             * +--------------------------------------------------------------+
+             *               ^                          ^       ^
+             *               |                          |       |
+             *              less                        k     great
              *
              * Invariants:
              *
@@ -194,16 +229,14 @@
              *    pivot1 <= all in [less, k)     <= pivot2
              *              all in (great, right) > pivot2
              *
-             * Pointer k is the first index of ?-part
+             * Pointer k is the first index of ?-part.
              */
             outer:
             for (int k = less; k <= great; k++) {
                 int ak = a[k];
                 if (ak < pivot1) { // Move a[k] to left part
-                    if (k != less) {
-                        a[k] = a[less];
-                        a[less] = ak;
-                    }
+                    a[k] = a[less];
+                    a[less] = ak;
                     less++;
                 } else if (ak > pivot2) { // Move a[k] to right part
                     while (a[great] > pivot2) {
@@ -213,26 +246,107 @@
                     }
                     if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = a[great];
-                        a[great--] = ak;
+                        a[less] = a[great];
+                        less++;
                     } else { // pivot1 <= a[great] <= pivot2
                         a[k] = a[great];
-                        a[great--] = ak;
+                    }
+                    a[great] = ak;
+                    great--;
+                }
+            }
+
+            // Swap pivots into their final positions
+            a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
+            a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+            // Sort left and right parts recursively, excluding known pivots
+            sort(a, left, less - 2, leftmost);
+            sort(a, great + 2, right, false);
+
+            /*
+             * If center part is too large (comprises > 5/7 of the array),
+             * swap internal pivot values to ends.
+             */
+            if (less < e1 && e5 < great) {
+                /*
+                 * Skip elements, which are equal to pivot values.
+                 */
+                while (a[less] == pivot1) {
+                    less++;
+                }
+                while (a[great] == pivot2) {
+                    great--;
+                }
+
+                /*
+                 * Partitioning:
+                 *
+                 *   left part         center part                  right part
+                 * +----------------------------------------------------------+
+                 * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
+                 * +----------------------------------------------------------+
+                 *              ^                        ^       ^
+                 *              |                        |       |
+                 *             less                      k     great
+                 *
+                 * Invariants:
+                 *
+                 *              all in (*,  less) == pivot1
+                 *     pivot1 < all in [less,  k)  < pivot2
+                 *              all in (great, *) == pivot2
+                 *
+                 * Pointer k is the first index of ?-part.
+                 */
+                outer:
+                for (int k = less; k <= great; k++) {
+                    int ak = a[k];
+                    if (ak == pivot1) { // Move a[k] to left part
+                        a[k] = a[less];
+                        a[less] = ak;
+                        less++;
+                    } else if (ak == pivot2) { // Move a[k] to right part
+                        while (a[great] == pivot2) {
+                            if (great-- == k) {
+                                break outer;
+                            }
+                        }
+                        if (a[great] == pivot1) {
+                            a[k] = a[less];
+                            /*
+                             * Even though a[great] equals to pivot1, the
+                             * assignment a[less] = pivot1 may be incorrect,
+                             * if a[great] and pivot1 are floating-point zeros
+                             * of different signs. Therefore in float and
+                             * double sorting methods we have to use more
+                             * accurate assignment a[less] = a[great].
+                             */
+                            a[less] = pivot1;
+                            less++;
+                        } else { // pivot1 < a[great] < pivot2
+                            a[k] = a[great];
+                        }
+                        a[great] = ak;
+                        great--;
                     }
                 }
             }
+
+            // Sort center part recursively
+            sort(a, less, great, false);
+
         } else { // Pivots are equal
             /*
-             * Partition degenerates to the traditional 3-way,
-             * or "Dutch National Flag", partition:
+             * Partition degenerates to the traditional 3-way
+             * (or "Dutch National Flag") schema:
              *
-             *   left part   center part            right part
-             * +----------------------------------------------+
-             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
-             * +----------------------------------------------+
-             *              ^            ^       ^
-             *              |            |       |
-             *             less          k     great
+             *   left part    center part              right part
+             * +-------------------------------------------------+
+             * |  < pivot  |   == pivot   |     ?    |  > pivot  |
+             * +-------------------------------------------------+
+             *              ^              ^        ^
+             *              |              |        |
+             *             less            k      great
              *
              * Invariants:
              *
@@ -240,20 +354,19 @@
              *   all in [less, k)     == pivot
              *   all in (great, right) > pivot
              *
-             * Pointer k is the first index of ?-part
+             * Pointer k is the first index of ?-part.
              */
-            for (int k = less; k <= great; k++) {
-                int ak = a[k];
-                if (ak == pivot1) {
+            for (int k = left; k <= great; k++) {
+                if (a[k] == pivot1) {
                     continue;
                 }
+                int ak = a[k];
+
                 if (ak < pivot1) { // Move a[k] to left part
-                    if (k != less) {
-                        a[k] = a[less];
-                        a[less] = ak;
-                    }
+                    a[k] = a[less];
+                    a[less] = ak;
                     less++;
-                } else { // (a[k] > pivot1) - Move a[k] to right part
+                } else { // a[k] > pivot1 - Move a[k] to right part
                     /*
                      * We know that pivot1 == a[e3] == pivot2. Thus, we know
                      * that great will still be >= k when the following loop
@@ -261,92 +374,33 @@
                      * In other words, a[e3] acts as a sentinel for great.
                      */
                     while (a[great] > pivot1) {
+                        // assert great > k;
                         great--;
                     }
                     if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = a[great];
-                        a[great--] = ak;
+                        a[less] = a[great];
+                        less++;
                     } else { // a[great] == pivot1
+                        /*
+                         * Even though a[great] equals to pivot1, the
+                         * assignment a[k] = pivot1 may be incorrect,
+                         * if a[great] and pivot1 are floating-point
+                         * zeros of different signs. Therefore in float
+                         * and double sorting methods we have to use
+                         * more accurate assignment a[k] = a[great].
+                         */
                         a[k] = pivot1;
-                        a[great--] = ak;
                     }
+                    a[great] = ak;
+                    great--;
                 }
             }
+
+            // Sort left and right parts recursively
+            sort(a, left, less - 1, leftmost);
+            sort(a, great + 1, right, false);
         }
-
-        // Swap pivots into their final positions
-        a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
-        a[right] = a[great + 1]; a[great + 1] = pivot2;
-
-        // Sort left and right parts recursively, excluding known pivot values
-        doSort(a, left,   less - 2);
-        doSort(a, great + 2, right);
-
-        /*
-         * If pivot1 == pivot2, all elements from center
-         * part are equal and, therefore, already sorted
-         */
-        if (!pivotsDiffer) {
-            return;
-        }
-
-        /*
-         * If center part is too large (comprises > 2/3 of the array),
-         * swap internal pivot values to ends
-         */
-        if (less < e1 && great > e5) {
-            while (a[less] == pivot1) {
-                less++;
-            }
-            while (a[great] == pivot2) {
-                great--;
-            }
-
-            /*
-             * Partitioning:
-             *
-             *   left part       center part                   right part
-             * +----------------------------------------------------------+
-             * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
-             * +----------------------------------------------------------+
-             *              ^                        ^       ^
-             *              |                        |       |
-             *             less                      k     great
-             *
-             * Invariants:
-             *
-             *              all in (*, less)  == pivot1
-             *     pivot1 < all in [less, k)   < pivot2
-             *              all in (great, *) == pivot2
-             *
-             * Pointer k is the first index of ?-part
-             */
-            outer:
-            for (int k = less; k <= great; k++) {
-                int ak = a[k];
-                if (ak == pivot2) { // Move a[k] to right part
-                    while (a[great] == pivot2) {
-                        if (great-- == k) {
-                            break outer;
-                        }
-                    }
-                    if (a[great] == pivot1) {
-                        a[k] = a[less];
-                        a[less++] = pivot1;
-                    } else { // pivot1 < a[great] < pivot2
-                        a[k] = a[great];
-                    }
-                    a[great--] = pivot2;
-                } else if (ak == pivot1) { // Move a[k] to left part
-                    a[k] = a[less];
-                    a[less++] = pivot1;
-                }
-            }
-        }
-
-        // Sort center part recursively, excluding known pivot values
-        doSort(a, less, great);
     }
 
     /**
@@ -355,7 +409,7 @@
      * @param a the array to be sorted
      */
     public static void sort(long[] a) {
-        doSort(a, 0, a.length - 1);
+        sort(a, 0, a.length - 1, true);
     }
 
     /**
@@ -373,98 +427,132 @@
      */
     public static void sort(long[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        doSort(a, fromIndex, toIndex - 1);
+        sort(a, fromIndex, toIndex - 1, true);
     }
 
     /**
-     * Sorts the specified range of the array into ascending order. This
-     * method differs from the public {@code sort} method in that the
-     * {@code right} index is inclusive, and it does no range checking on
-     * {@code left} or {@code right}.
+     * Sorts the specified range of the array into ascending order by the
+     * Dual-Pivot Quicksort algorithm. This method differs from the public
+     * {@code sort} method in that the {@code right} index is inclusive,
+     * it does no range checking on {@code left} or {@code right}, and has
+     * boolean flag whether insertion sort with sentinel is used or not.
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param leftmost indicates if the part is the most left in the range
      */
-    private static void doSort(long[] a, int left, int right) {
+    private static void sort(long[] a, int left, int right, boolean leftmost) {
+        int length = right - left + 1;
+
         // Use insertion sort on tiny arrays
-        if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
-            for (int i = left + 1; i <= right; i++) {
-                long ai = a[i];
-                int j;
-                for (j = i - 1; j >= left && ai < a[j]; j--) {
-                    a[j + 1] = a[j];
+        if (length < INSERTION_SORT_THRESHOLD) {
+            if (!leftmost) {
+                /*
+                 * Every element in adjoining part plays the role
+                 * of sentinel, therefore this allows us to avoid
+                 * the j >= left check on each iteration.
+                 */
+                for (int j, i = left + 1; i <= right; i++) {
+                    long ai = a[i];
+                    for (j = i - 1; ai < a[j]; j--) {
+                        // assert j >= left;
+                        a[j + 1] = a[j];
+                    }
+                    a[j + 1] = ai;
                 }
-                a[j + 1] = ai;
+            } else {
+                /*
+                 * For case of leftmost part traditional (without a sentinel)
+                 * insertion sort, optimized for server JVM, is used.
+                 */
+                for (int i = left, j = i; i < right; j = ++i) {
+                    long ai = a[i + 1];
+                    while (ai < a[j]) {
+                        a[j + 1] = a[j];
+                        if (j-- == left) {
+                            break;
+                        }
+                    }
+                    a[j + 1] = ai;
+                }
             }
-        } else { // Use Dual-Pivot Quicksort on large arrays
-            dualPivotQuicksort(a, left, right);
+            return;
         }
-    }
 
-    /**
-     * Sorts the specified range of the array into ascending order by the
-     * Dual-Pivot Quicksort algorithm.
-     *
-     * @param a the array to be sorted
-     * @param left the index of the first element, inclusive, to be sorted
-     * @param right the index of the last element, inclusive, to be sorted
-     */
-    private static void dualPivotQuicksort(long[] a, int left, int right) {
-        // Compute indices of five evenly spaced elements
-        int sixth = (right - left + 1) / 6;
-        int e1 = left  + sixth;
-        int e5 = right - sixth;
+        // Inexpensive approximation of length / 7
+        int seventh = (length >>> 3) + (length >>> 6) + 1;
+
+        /*
+         * Sort five evenly spaced elements around (and including) the
+         * center element in the range. These elements will be used for
+         * pivot selection as described below. The choice for spacing
+         * these elements was empirically determined to work well on
+         * a wide variety of inputs.
+         */
         int e3 = (left + right) >>> 1; // The midpoint
-        int e4 = e3 + sixth;
-        int e2 = e3 - sixth;
+        int e2 = e3 - seventh;
+        int e1 = e2 - seventh;
+        int e4 = e3 + seventh;
+        int e5 = e4 + seventh;
 
-        // Sort these elements using a 5-element sorting network
-        long ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+        // Sort these elements using insertion sort
+        if (a[e2] < a[e1]) { long t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
 
-        if (ae1 > ae2) { long t = ae1; ae1 = ae2; ae2 = t; }
-        if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
-        if (ae1 > ae3) { long t = ae1; ae1 = ae3; ae3 = t; }
-        if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
-        if (ae1 > ae4) { long t = ae1; ae1 = ae4; ae4 = t; }
-        if (ae3 > ae4) { long t = ae3; ae3 = ae4; ae4 = t; }
-        if (ae2 > ae5) { long t = ae2; ae2 = ae5; ae5 = t; }
-        if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
-        if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
-
-        a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+        if (a[e3] < a[e2]) { long t = a[e3]; a[e3] = a[e2]; a[e2] = t;
+            if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+        }
+        if (a[e4] < a[e3]) { long t = a[e4]; a[e4] = a[e3]; a[e3] = t;
+            if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+                if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+            }
+        }
+        if (a[e5] < a[e4]) { long t = a[e5]; a[e5] = a[e4]; a[e4] = t;
+            if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
+                if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+                    if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+                }
+            }
+        }
 
         /*
          * Use the second and fourth of the five sorted elements as pivots.
          * These values are inexpensive approximations of the first and
          * second terciles of the array. Note that pivot1 <= pivot2.
-         *
-         * The pivots are stored in local variables, and the first and
-         * the last of the elements to be sorted are moved to the locations
-         * formerly occupied by the pivots. When partitioning is complete,
-         * the pivots are swapped back into their final positions, and
-         * excluded from subsequent sorting.
          */
-        long pivot1 = ae2; a[e2] = a[left];
-        long pivot2 = ae4; a[e4] = a[right];
+        long pivot1 = a[e2];
+        long pivot2 = a[e4];
 
         // Pointers
-        int less  = left  + 1; // The index of first element of center part
-        int great = right - 1; // The index before first element of right part
+        int less  = left;  // The index of the first element of center part
+        int great = right; // The index before the first element of right part
 
-        boolean pivotsDiffer = (pivot1 != pivot2);
+        if (pivot1 != pivot2) {
+            /*
+             * The first and the last elements to be sorted are moved to the
+             * locations formerly occupied by the pivots. When partitioning
+             * is complete, the pivots are swapped back into their final
+             * positions, and excluded from subsequent sorting.
+             */
+            a[e2] = a[left];
+            a[e4] = a[right];
 
-        if (pivotsDiffer) {
+            /*
+             * Skip elements, which are less or greater than pivot values.
+             */
+            while (a[++less] < pivot1);
+            while (a[--great] > pivot2);
+
             /*
              * Partitioning:
              *
-             *   left part         center part                    right part
-             * +------------------------------------------------------------+
-             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
-             * +------------------------------------------------------------+
-             *              ^                          ^       ^
-             *              |                          |       |
-             *             less                        k     great
+             *   left part           center part                   right part
+             * +--------------------------------------------------------------+
+             * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
+             * +--------------------------------------------------------------+
+             *               ^                          ^       ^
+             *               |                          |       |
+             *              less                        k     great
              *
              * Invariants:
              *
@@ -472,16 +560,14 @@
              *    pivot1 <= all in [less, k)     <= pivot2
              *              all in (great, right) > pivot2
              *
-             * Pointer k is the first index of ?-part
+             * Pointer k is the first index of ?-part.
              */
             outer:
             for (int k = less; k <= great; k++) {
                 long ak = a[k];
                 if (ak < pivot1) { // Move a[k] to left part
-                    if (k != less) {
-                        a[k] = a[less];
-                        a[less] = ak;
-                    }
+                    a[k] = a[less];
+                    a[less] = ak;
                     less++;
                 } else if (ak > pivot2) { // Move a[k] to right part
                     while (a[great] > pivot2) {
@@ -491,26 +577,107 @@
                     }
                     if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = a[great];
-                        a[great--] = ak;
+                        a[less] = a[great];
+                        less++;
                     } else { // pivot1 <= a[great] <= pivot2
                         a[k] = a[great];
-                        a[great--] = ak;
+                    }
+                    a[great] = ak;
+                    great--;
+                }
+            }
+
+            // Swap pivots into their final positions
+            a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
+            a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+            // Sort left and right parts recursively, excluding known pivots
+            sort(a, left, less - 2, leftmost);
+            sort(a, great + 2, right, false);
+
+            /*
+             * If center part is too large (comprises > 5/7 of the array),
+             * swap internal pivot values to ends.
+             */
+            if (less < e1 && e5 < great) {
+                /*
+                 * Skip elements, which are equal to pivot values.
+                 */
+                while (a[less] == pivot1) {
+                    less++;
+                }
+                while (a[great] == pivot2) {
+                    great--;
+                }
+
+                /*
+                 * Partitioning:
+                 *
+                 *   left part         center part                  right part
+                 * +----------------------------------------------------------+
+                 * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
+                 * +----------------------------------------------------------+
+                 *              ^                        ^       ^
+                 *              |                        |       |
+                 *             less                      k     great
+                 *
+                 * Invariants:
+                 *
+                 *              all in (*,  less) == pivot1
+                 *     pivot1 < all in [less,  k)  < pivot2
+                 *              all in (great, *) == pivot2
+                 *
+                 * Pointer k is the first index of ?-part.
+                 */
+                outer:
+                for (int k = less; k <= great; k++) {
+                    long ak = a[k];
+                    if (ak == pivot1) { // Move a[k] to left part
+                        a[k] = a[less];
+                        a[less] = ak;
+                        less++;
+                    } else if (ak == pivot2) { // Move a[k] to right part
+                        while (a[great] == pivot2) {
+                            if (great-- == k) {
+                                break outer;
+                            }
+                        }
+                        if (a[great] == pivot1) {
+                            a[k] = a[less];
+                            /*
+                             * Even though a[great] equals to pivot1, the
+                             * assignment a[less] = pivot1 may be incorrect,
+                             * if a[great] and pivot1 are floating-point zeros
+                             * of different signs. Therefore in float and
+                             * double sorting methods we have to use more
+                             * accurate assignment a[less] = a[great].
+                             */
+                            a[less] = pivot1;
+                            less++;
+                        } else { // pivot1 < a[great] < pivot2
+                            a[k] = a[great];
+                        }
+                        a[great] = ak;
+                        great--;
                     }
                 }
             }
+
+            // Sort center part recursively
+            sort(a, less, great, false);
+
         } else { // Pivots are equal
             /*
-             * Partition degenerates to the traditional 3-way,
-             * or "Dutch National Flag", partition:
+             * Partition degenerates to the traditional 3-way
+             * (or "Dutch National Flag") schema:
              *
-             *   left part   center part            right part
-             * +----------------------------------------------+
-             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
-             * +----------------------------------------------+
-             *              ^            ^       ^
-             *              |            |       |
-             *             less          k     great
+             *   left part    center part              right part
+             * +-------------------------------------------------+
+             * |  < pivot  |   == pivot   |     ?    |  > pivot  |
+             * +-------------------------------------------------+
+             *              ^              ^        ^
+             *              |              |        |
+             *             less            k      great
              *
              * Invariants:
              *
@@ -518,20 +685,19 @@
              *   all in [less, k)     == pivot
              *   all in (great, right) > pivot
              *
-             * Pointer k is the first index of ?-part
+             * Pointer k is the first index of ?-part.
              */
-            for (int k = less; k <= great; k++) {
-                long ak = a[k];
-                if (ak == pivot1) {
+            for (int k = left; k <= great; k++) {
+                if (a[k] == pivot1) {
                     continue;
                 }
+                long ak = a[k];
+
                 if (ak < pivot1) { // Move a[k] to left part
-                    if (k != less) {
-                        a[k] = a[less];
-                        a[less] = ak;
-                    }
+                    a[k] = a[less];
+                    a[less] = ak;
                     less++;
-                } else { // (a[k] > pivot1) - Move a[k] to right part
+                } else { // a[k] > pivot1 - Move a[k] to right part
                     /*
                      * We know that pivot1 == a[e3] == pivot2. Thus, we know
                      * that great will still be >= k when the following loop
@@ -539,92 +705,33 @@
                      * In other words, a[e3] acts as a sentinel for great.
                      */
                     while (a[great] > pivot1) {
+                        // assert great > k;
                         great--;
                     }
                     if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = a[great];
-                        a[great--] = ak;
+                        a[less] = a[great];
+                        less++;
                     } else { // a[great] == pivot1
+                        /*
+                         * Even though a[great] equals to pivot1, the
+                         * assignment a[k] = pivot1 may be incorrect,
+                         * if a[great] and pivot1 are floating-point
+                         * zeros of different signs. Therefore in float
+                         * and double sorting methods we have to use
+                         * more accurate assignment a[k] = a[great].
+                         */
                         a[k] = pivot1;
-                        a[great--] = ak;
                     }
+                    a[great] = ak;
+                    great--;
                 }
             }
+
+            // Sort left and right parts recursively
+            sort(a, left, less - 1, leftmost);
+            sort(a, great + 1, right, false);
         }
-
-        // Swap pivots into their final positions
-        a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
-        a[right] = a[great + 1]; a[great + 1] = pivot2;
-
-        // Sort left and right parts recursively, excluding known pivot values
-        doSort(a, left,   less - 2);
-        doSort(a, great + 2, right);
-
-        /*
-         * If pivot1 == pivot2, all elements from center
-         * part are equal and, therefore, already sorted
-         */
-        if (!pivotsDiffer) {
-            return;
-        }
-
-        /*
-         * If center part is too large (comprises > 2/3 of the array),
-         * swap internal pivot values to ends
-         */
-        if (less < e1 && great > e5) {
-            while (a[less] == pivot1) {
-                less++;
-            }
-            while (a[great] == pivot2) {
-                great--;
-            }
-
-            /*
-             * Partitioning:
-             *
-             *   left part       center part                   right part
-             * +----------------------------------------------------------+
-             * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
-             * +----------------------------------------------------------+
-             *              ^                        ^       ^
-             *              |                        |       |
-             *             less                      k     great
-             *
-             * Invariants:
-             *
-             *              all in (*, less)  == pivot1
-             *     pivot1 < all in [less, k)   < pivot2
-             *              all in (great, *) == pivot2
-             *
-             * Pointer k is the first index of ?-part
-             */
-            outer:
-            for (int k = less; k <= great; k++) {
-                long ak = a[k];
-                if (ak == pivot2) { // Move a[k] to right part
-                    while (a[great] == pivot2) {
-                        if (great-- == k) {
-                            break outer;
-                        }
-                    }
-                    if (a[great] == pivot1) {
-                        a[k] = a[less];
-                        a[less++] = pivot1;
-                    } else { // pivot1 < a[great] < pivot2
-                        a[k] = a[great];
-                    }
-                    a[great--] = pivot2;
-                } else if (ak == pivot1) { // Move a[k] to left part
-                    a[k] = a[less];
-                    a[less++] = pivot1;
-                }
-            }
-        }
-
-        // Sort center part recursively, excluding known pivot values
-        doSort(a, less, great);
     }
 
     /**
@@ -633,7 +740,11 @@
      * @param a the array to be sorted
      */
     public static void sort(short[] a) {
-        doSort(a, 0, a.length - 1);
+        if (a.length > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
+            countingSort(a, 0, a.length - 1);
+        } else {
+            sort(a, 0, a.length - 1, true);
+        }
     }
 
     /**
@@ -651,115 +762,166 @@
      */
     public static void sort(short[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        doSort(a, fromIndex, toIndex - 1);
+
+        if (toIndex - fromIndex > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
+            countingSort(a, fromIndex, toIndex - 1);
+        } else {
+            sort(a, fromIndex, toIndex - 1, true);
+        }
     }
 
     /** The number of distinct short values. */
     private static final int NUM_SHORT_VALUES = 1 << 16;
 
     /**
-     * Sorts the specified range of the array into ascending order. This
-     * method differs from the public {@code sort} method in that the
-     * {@code right} index is inclusive, and it does no range checking on
-     * {@code left} or {@code right}.
+     * Sorts the specified range of the array by counting sort.
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
      */
-    private static void doSort(short[] a, int left, int right) {
-        // Use insertion sort on tiny arrays
-        if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
-            for (int i = left + 1; i <= right; i++) {
-                short ai = a[i];
-                int j;
-                for (j = i - 1; j >= left && ai < a[j]; j--) {
-                    a[j + 1] = a[j];
-                }
-                a[j + 1] = ai;
+    private static void countingSort(short[] a, int left, int right) {
+        int[] count = new int[NUM_SHORT_VALUES];
+
+        for (int i = left; i <= right; i++) {
+            count[a[i] - Short.MIN_VALUE]++;
+        }
+        for (int i = NUM_SHORT_VALUES - 1, k = right; k >= left; i--) {
+            while (count[i] == 0) {
+                i--;
             }
-        } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
-            // Use counting sort on huge arrays
-            int[] count = new int[NUM_SHORT_VALUES];
+            short value = (short) (i + Short.MIN_VALUE);
+            int s = count[i];
 
-            for (int i = left; i <= right; i++) {
-                count[a[i] - Short.MIN_VALUE]++;
-            }
-            for (int i = 0, k = left; i < count.length && k <= right; i++) {
-                short value = (short) (i + Short.MIN_VALUE);
-
-                for (int s = count[i]; s > 0; s--) {
-                    a[k++] = value;
-               }
-            }
-        } else { // Use Dual-Pivot Quicksort on large arrays
-            dualPivotQuicksort(a, left, right);
+            do {
+                a[k--] = value;
+            } while (--s > 0);
         }
     }
 
     /**
      * Sorts the specified range of the array into ascending order by the
-     * Dual-Pivot Quicksort algorithm.
+     * Dual-Pivot Quicksort algorithm. This method differs from the public
+     * {@code sort} method in that the {@code right} index is inclusive,
+     * it does no range checking on {@code left} or {@code right}, and has
+     * boolean flag whether insertion sort with sentinel is used or not.
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param leftmost indicates if the part is the most left in the range
      */
-    private static void dualPivotQuicksort(short[] a, int left, int right) {
-        // Compute indices of five evenly spaced elements
-        int sixth = (right - left + 1) / 6;
-        int e1 = left  + sixth;
-        int e5 = right - sixth;
+    private static void sort(short[] a, int left, int right,boolean leftmost) {
+        int length = right - left + 1;
+
+        // Use insertion sort on tiny arrays
+        if (length < INSERTION_SORT_THRESHOLD) {
+            if (!leftmost) {
+                /*
+                 * Every element in adjoining part plays the role
+                 * of sentinel, therefore this allows us to avoid
+                 * the j >= left check on each iteration.
+                 */
+                for (int j, i = left + 1; i <= right; i++) {
+                    short ai = a[i];
+                    for (j = i - 1; ai < a[j]; j--) {
+                        // assert j >= left;
+                        a[j + 1] = a[j];
+                    }
+                    a[j + 1] = ai;
+                }
+            } else {
+                /*
+                 * For case of leftmost part traditional (without a sentinel)
+                 * insertion sort, optimized for server JVM, is used.
+                 */
+                for (int i = left, j = i; i < right; j = ++i) {
+                    short ai = a[i + 1];
+                    while (ai < a[j]) {
+                        a[j + 1] = a[j];
+                        if (j-- == left) {
+                            break;
+                        }
+                    }
+                    a[j + 1] = ai;
+                }
+            }
+            return;
+        }
+
+        // Inexpensive approximation of length / 7
+        int seventh = (length >>> 3) + (length >>> 6) + 1;
+
+        /*
+         * Sort five evenly spaced elements around (and including) the
+         * center element in the range. These elements will be used for
+         * pivot selection as described below. The choice for spacing
+         * these elements was empirically determined to work well on
+         * a wide variety of inputs.
+         */
         int e3 = (left + right) >>> 1; // The midpoint
-        int e4 = e3 + sixth;
-        int e2 = e3 - sixth;
+        int e2 = e3 - seventh;
+        int e1 = e2 - seventh;
+        int e4 = e3 + seventh;
+        int e5 = e4 + seventh;
 
-        // Sort these elements using a 5-element sorting network
-        short ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+        // Sort these elements using insertion sort
+        if (a[e2] < a[e1]) { short t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
 
-        if (ae1 > ae2) { short t = ae1; ae1 = ae2; ae2 = t; }
-        if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; }
-        if (ae1 > ae3) { short t = ae1; ae1 = ae3; ae3 = t; }
-        if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; }
-        if (ae1 > ae4) { short t = ae1; ae1 = ae4; ae4 = t; }
-        if (ae3 > ae4) { short t = ae3; ae3 = ae4; ae4 = t; }
-        if (ae2 > ae5) { short t = ae2; ae2 = ae5; ae5 = t; }
-        if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; }
-        if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; }
-
-        a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+        if (a[e3] < a[e2]) { short t = a[e3]; a[e3] = a[e2]; a[e2] = t;
+            if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+        }
+        if (a[e4] < a[e3]) { short t = a[e4]; a[e4] = a[e3]; a[e3] = t;
+            if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+                if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+            }
+        }
+        if (a[e5] < a[e4]) { short t = a[e5]; a[e5] = a[e4]; a[e4] = t;
+            if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
+                if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+                    if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+                }
+            }
+        }
 
         /*
          * Use the second and fourth of the five sorted elements as pivots.
          * These values are inexpensive approximations of the first and
          * second terciles of the array. Note that pivot1 <= pivot2.
-         *
-         * The pivots are stored in local variables, and the first and
-         * the last of the elements to be sorted are moved to the locations
-         * formerly occupied by the pivots. When partitioning is complete,
-         * the pivots are swapped back into their final positions, and
-         * excluded from subsequent sorting.
          */
-        short pivot1 = ae2; a[e2] = a[left];
-        short pivot2 = ae4; a[e4] = a[right];
+        short pivot1 = a[e2];
+        short pivot2 = a[e4];
 
         // Pointers
-        int less  = left  + 1; // The index of first element of center part
-        int great = right - 1; // The index before first element of right part
+        int less  = left;  // The index of the first element of center part
+        int great = right; // The index before the first element of right part
 
-        boolean pivotsDiffer = (pivot1 != pivot2);
+        if (pivot1 != pivot2) {
+            /*
+             * The first and the last elements to be sorted are moved to the
+             * locations formerly occupied by the pivots. When partitioning
+             * is complete, the pivots are swapped back into their final
+             * positions, and excluded from subsequent sorting.
+             */
+            a[e2] = a[left];
+            a[e4] = a[right];
 
-        if (pivotsDiffer) {
+            /*
+             * Skip elements, which are less or greater than pivot values.
+             */
+            while (a[++less] < pivot1);
+            while (a[--great] > pivot2);
+
             /*
              * Partitioning:
              *
-             *   left part         center part                    right part
-             * +------------------------------------------------------------+
-             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
-             * +------------------------------------------------------------+
-             *              ^                          ^       ^
-             *              |                          |       |
-             *             less                        k     great
+             *   left part           center part                   right part
+             * +--------------------------------------------------------------+
+             * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
+             * +--------------------------------------------------------------+
+             *               ^                          ^       ^
+             *               |                          |       |
+             *              less                        k     great
              *
              * Invariants:
              *
@@ -767,16 +929,14 @@
              *    pivot1 <= all in [less, k)     <= pivot2
              *              all in (great, right) > pivot2
              *
-             * Pointer k is the first index of ?-part
+             * Pointer k is the first index of ?-part.
              */
             outer:
             for (int k = less; k <= great; k++) {
                 short ak = a[k];
                 if (ak < pivot1) { // Move a[k] to left part
-                    if (k != less) {
-                        a[k] = a[less];
-                        a[less] = ak;
-                    }
+                    a[k] = a[less];
+                    a[less] = ak;
                     less++;
                 } else if (ak > pivot2) { // Move a[k] to right part
                     while (a[great] > pivot2) {
@@ -786,26 +946,107 @@
                     }
                     if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = a[great];
-                        a[great--] = ak;
+                        a[less] = a[great];
+                        less++;
                     } else { // pivot1 <= a[great] <= pivot2
                         a[k] = a[great];
-                        a[great--] = ak;
+                    }
+                    a[great] = ak;
+                    great--;
+                }
+            }
+
+            // Swap pivots into their final positions
+            a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
+            a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+            // Sort left and right parts recursively, excluding known pivots
+            sort(a, left, less - 2, leftmost);
+            sort(a, great + 2, right, false);
+
+            /*
+             * If center part is too large (comprises > 5/7 of the array),
+             * swap internal pivot values to ends.
+             */
+            if (less < e1 && e5 < great) {
+                /*
+                 * Skip elements, which are equal to pivot values.
+                 */
+                while (a[less] == pivot1) {
+                    less++;
+                }
+                while (a[great] == pivot2) {
+                    great--;
+                }
+
+                /*
+                 * Partitioning:
+                 *
+                 *   left part         center part                  right part
+                 * +----------------------------------------------------------+
+                 * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
+                 * +----------------------------------------------------------+
+                 *              ^                        ^       ^
+                 *              |                        |       |
+                 *             less                      k     great
+                 *
+                 * Invariants:
+                 *
+                 *              all in (*,  less) == pivot1
+                 *     pivot1 < all in [less,  k)  < pivot2
+                 *              all in (great, *) == pivot2
+                 *
+                 * Pointer k is the first index of ?-part.
+                 */
+                outer:
+                for (int k = less; k <= great; k++) {
+                    short ak = a[k];
+                    if (ak == pivot1) { // Move a[k] to left part
+                        a[k] = a[less];
+                        a[less] = ak;
+                        less++;
+                    } else if (ak == pivot2) { // Move a[k] to right part
+                        while (a[great] == pivot2) {
+                            if (great-- == k) {
+                                break outer;
+                            }
+                        }
+                        if (a[great] == pivot1) {
+                            a[k] = a[less];
+                            /*
+                             * Even though a[great] equals to pivot1, the
+                             * assignment a[less] = pivot1 may be incorrect,
+                             * if a[great] and pivot1 are floating-point zeros
+                             * of different signs. Therefore in float and
+                             * double sorting methods we have to use more
+                             * accurate assignment a[less] = a[great].
+                             */
+                            a[less] = pivot1;
+                            less++;
+                        } else { // pivot1 < a[great] < pivot2
+                            a[k] = a[great];
+                        }
+                        a[great] = ak;
+                        great--;
                     }
                 }
             }
+
+            // Sort center part recursively
+            sort(a, less, great, false);
+
         } else { // Pivots are equal
             /*
-             * Partition degenerates to the traditional 3-way,
-             * or "Dutch National Flag", partition:
+             * Partition degenerates to the traditional 3-way
+             * (or "Dutch National Flag") schema:
              *
-             *   left part   center part            right part
-             * +----------------------------------------------+
-             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
-             * +----------------------------------------------+
-             *              ^            ^       ^
-             *              |            |       |
-             *             less          k     great
+             *   left part    center part              right part
+             * +-------------------------------------------------+
+             * |  < pivot  |   == pivot   |     ?    |  > pivot  |
+             * +-------------------------------------------------+
+             *              ^              ^        ^
+             *              |              |        |
+             *             less            k      great
              *
              * Invariants:
              *
@@ -813,20 +1054,19 @@
              *   all in [less, k)     == pivot
              *   all in (great, right) > pivot
              *
-             * Pointer k is the first index of ?-part
+             * Pointer k is the first index of ?-part.
              */
-            for (int k = less; k <= great; k++) {
-                short ak = a[k];
-                if (ak == pivot1) {
+            for (int k = left; k <= great; k++) {
+                if (a[k] == pivot1) {
                     continue;
                 }
+                short ak = a[k];
+
                 if (ak < pivot1) { // Move a[k] to left part
-                    if (k != less) {
-                        a[k] = a[less];
-                        a[less] = ak;
-                    }
+                    a[k] = a[less];
+                    a[less] = ak;
                     less++;
-                } else { // (a[k] > pivot1) - Move a[k] to right part
+                } else { // a[k] > pivot1 - Move a[k] to right part
                     /*
                      * We know that pivot1 == a[e3] == pivot2. Thus, we know
                      * that great will still be >= k when the following loop
@@ -834,92 +1074,33 @@
                      * In other words, a[e3] acts as a sentinel for great.
                      */
                     while (a[great] > pivot1) {
+                        // assert great > k;
                         great--;
                     }
                     if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = a[great];
-                        a[great--] = ak;
+                        a[less] = a[great];
+                        less++;
                     } else { // a[great] == pivot1
+                        /*
+                         * Even though a[great] equals to pivot1, the
+                         * assignment a[k] = pivot1 may be incorrect,
+                         * if a[great] and pivot1 are floating-point
+                         * zeros of different signs. Therefore in float
+                         * and double sorting methods we have to use
+                         * more accurate assignment a[k] = a[great].
+                         */
                         a[k] = pivot1;
-                        a[great--] = ak;
                     }
+                    a[great] = ak;
+                    great--;
                 }
             }
+
+            // Sort left and right parts recursively
+            sort(a, left, less - 1, leftmost);
+            sort(a, great + 1, right, false);
         }
-
-        // Swap pivots into their final positions
-        a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
-        a[right] = a[great + 1]; a[great + 1] = pivot2;
-
-        // Sort left and right parts recursively, excluding known pivot values
-        doSort(a, left,   less - 2);
-        doSort(a, great + 2, right);
-
-        /*
-         * If pivot1 == pivot2, all elements from center
-         * part are equal and, therefore, already sorted
-         */
-        if (!pivotsDiffer) {
-            return;
-        }
-
-        /*
-         * If center part is too large (comprises > 2/3 of the array),
-         * swap internal pivot values to ends
-         */
-        if (less < e1 && great > e5) {
-            while (a[less] == pivot1) {
-                less++;
-            }
-            while (a[great] == pivot2) {
-                great--;
-            }
-
-            /*
-             * Partitioning:
-             *
-             *   left part       center part                   right part
-             * +----------------------------------------------------------+
-             * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
-             * +----------------------------------------------------------+
-             *              ^                        ^       ^
-             *              |                        |       |
-             *             less                      k     great
-             *
-             * Invariants:
-             *
-             *              all in (*, less)  == pivot1
-             *     pivot1 < all in [less, k)   < pivot2
-             *              all in (great, *) == pivot2
-             *
-             * Pointer k is the first index of ?-part
-             */
-            outer:
-            for (int k = less; k <= great; k++) {
-                short ak = a[k];
-                if (ak == pivot2) { // Move a[k] to right part
-                    while (a[great] == pivot2) {
-                        if (great-- == k) {
-                            break outer;
-                        }
-                    }
-                    if (a[great] == pivot1) {
-                        a[k] = a[less];
-                        a[less++] = pivot1;
-                    } else { // pivot1 < a[great] < pivot2
-                        a[k] = a[great];
-                    }
-                    a[great--] = pivot2;
-                } else if (ak == pivot1) { // Move a[k] to left part
-                    a[k] = a[less];
-                    a[less++] = pivot1;
-                }
-            }
-        }
-
-        // Sort center part recursively, excluding known pivot values
-        doSort(a, less, great);
     }
 
     /**
@@ -928,7 +1109,11 @@
      * @param a the array to be sorted
      */
     public static void sort(char[] a) {
-        doSort(a, 0, a.length - 1);
+        if (a.length > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
+            countingSort(a, 0, a.length - 1);
+        } else {
+            sort(a, 0, a.length - 1, true);
+        }
     }
 
     /**
@@ -946,113 +1131,166 @@
      */
     public static void sort(char[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        doSort(a, fromIndex, toIndex - 1);
+
+        if (toIndex - fromIndex > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
+            countingSort(a, fromIndex, toIndex - 1);
+        } else {
+            sort(a, fromIndex, toIndex - 1, true);
+        }
     }
 
     /** The number of distinct char values. */
     private static final int NUM_CHAR_VALUES = 1 << 16;
 
     /**
-     * Sorts the specified range of the array into ascending order. This
-     * method differs from the public {@code sort} method in that the
-     * {@code right} index is inclusive, and it does no range checking on
-     * {@code left} or {@code right}.
+     * Sorts the specified range of the array by counting sort.
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
      */
-    private static void doSort(char[] a, int left, int right) {
-        // Use insertion sort on tiny arrays
-        if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
-            for (int i = left + 1; i <= right; i++) {
-                char ai = a[i];
-                int j;
-                for (j = i - 1; j >= left && ai < a[j]; j--) {
-                    a[j + 1] = a[j];
-                }
-                a[j + 1] = ai;
+    private static void countingSort(char[] a, int left, int right) {
+        int[] count = new int[NUM_CHAR_VALUES];
+
+        for (int i = left; i <= right; i++) {
+            count[a[i]]++;
+        }
+        for (int i = 0, k = left; k <= right; i++) {
+            while (count[i] == 0) {
+                i++;
             }
-        } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
-            // Use counting sort on huge arrays
-            int[] count = new int[NUM_CHAR_VALUES];
+            char value = (char) i;
+            int s = count[i];
 
-            for (int i = left; i <= right; i++) {
-                count[a[i]]++;
-            }
-            for (int i = 0, k = left; i < count.length && k <= right; i++) {
-                for (int s = count[i]; s > 0; s--) {
-                    a[k++] = (char) i;
-               }
-            }
-        } else { // Use Dual-Pivot Quicksort on large arrays
-            dualPivotQuicksort(a, left, right);
+            do {
+                a[k++] = value;
+            } while (--s > 0);
         }
     }
 
     /**
      * Sorts the specified range of the array into ascending order by the
-     * Dual-Pivot Quicksort algorithm.
+     * Dual-Pivot Quicksort algorithm. This method differs from the public
+     * {@code sort} method in that the {@code right} index is inclusive,
+     * it does no range checking on {@code left} or {@code right}, and has
+     * boolean flag whether insertion sort with sentinel is used or not.
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param leftmost indicates if the part is the most left in the range
      */
-    private static void dualPivotQuicksort(char[] a, int left, int right) {
-        // Compute indices of five evenly spaced elements
-        int sixth = (right - left + 1) / 6;
-        int e1 = left  + sixth;
-        int e5 = right - sixth;
+    private static void sort(char[] a, int left, int right, boolean leftmost) {
+        int length = right - left + 1;
+
+        // Use insertion sort on tiny arrays
+        if (length < INSERTION_SORT_THRESHOLD) {
+            if (!leftmost) {
+                /*
+                 * Every element in adjoining part plays the role
+                 * of sentinel, therefore this allows us to avoid
+                 * the j >= left check on each iteration.
+                 */
+                for (int j, i = left + 1; i <= right; i++) {
+                    char ai = a[i];
+                    for (j = i - 1; ai < a[j]; j--) {
+                        // assert j >= left;
+                        a[j + 1] = a[j];
+                    }
+                    a[j + 1] = ai;
+                }
+            } else {
+                /*
+                 * For case of leftmost part traditional (without a sentinel)
+                 * insertion sort, optimized for server JVM, is used.
+                 */
+                for (int i = left, j = i; i < right; j = ++i) {
+                    char ai = a[i + 1];
+                    while (ai < a[j]) {
+                        a[j + 1] = a[j];
+                        if (j-- == left) {
+                            break;
+                        }
+                    }
+                    a[j + 1] = ai;
+                }
+            }
+            return;
+        }
+
+        // Inexpensive approximation of length / 7
+        int seventh = (length >>> 3) + (length >>> 6) + 1;
+
+        /*
+         * Sort five evenly spaced elements around (and including) the
+         * center element in the range. These elements will be used for
+         * pivot selection as described below. The choice for spacing
+         * these elements was empirically determined to work well on
+         * a wide variety of inputs.
+         */
         int e3 = (left + right) >>> 1; // The midpoint
-        int e4 = e3 + sixth;
-        int e2 = e3 - sixth;
+        int e2 = e3 - seventh;
+        int e1 = e2 - seventh;
+        int e4 = e3 + seventh;
+        int e5 = e4 + seventh;
 
-        // Sort these elements using a 5-element sorting network
-        char ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+        // Sort these elements using insertion sort
+        if (a[e2] < a[e1]) { char t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
 
-        if (ae1 > ae2) { char t = ae1; ae1 = ae2; ae2 = t; }
-        if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; }
-        if (ae1 > ae3) { char t = ae1; ae1 = ae3; ae3 = t; }
-        if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; }
-        if (ae1 > ae4) { char t = ae1; ae1 = ae4; ae4 = t; }
-        if (ae3 > ae4) { char t = ae3; ae3 = ae4; ae4 = t; }
-        if (ae2 > ae5) { char t = ae2; ae2 = ae5; ae5 = t; }
-        if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; }
-        if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; }
-
-        a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+        if (a[e3] < a[e2]) { char t = a[e3]; a[e3] = a[e2]; a[e2] = t;
+            if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+        }
+        if (a[e4] < a[e3]) { char t = a[e4]; a[e4] = a[e3]; a[e3] = t;
+            if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+                if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+            }
+        }
+        if (a[e5] < a[e4]) { char t = a[e5]; a[e5] = a[e4]; a[e4] = t;
+            if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
+                if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+                    if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+                }
+            }
+        }
 
         /*
          * Use the second and fourth of the five sorted elements as pivots.
          * These values are inexpensive approximations of the first and
          * second terciles of the array. Note that pivot1 <= pivot2.
-         *
-         * The pivots are stored in local variables, and the first and
-         * the last of the elements to be sorted are moved to the locations
-         * formerly occupied by the pivots. When partitioning is complete,
-         * the pivots are swapped back into their final positions, and
-         * excluded from subsequent sorting.
          */
-        char pivot1 = ae2; a[e2] = a[left];
-        char pivot2 = ae4; a[e4] = a[right];
+        char pivot1 = a[e2];
+        char pivot2 = a[e4];
 
         // Pointers
-        int less  = left  + 1; // The index of first element of center part
-        int great = right - 1; // The index before first element of right part
+        int less  = left;  // The index of the first element of center part
+        int great = right; // The index before the first element of right part
 
-        boolean pivotsDiffer = (pivot1 != pivot2);
+        if (pivot1 != pivot2) {
+            /*
+             * The first and the last elements to be sorted are moved to the
+             * locations formerly occupied by the pivots. When partitioning
+             * is complete, the pivots are swapped back into their final
+             * positions, and excluded from subsequent sorting.
+             */
+            a[e2] = a[left];
+            a[e4] = a[right];
 
-        if (pivotsDiffer) {
+            /*
+             * Skip elements, which are less or greater than pivot values.
+             */
+            while (a[++less] < pivot1);
+            while (a[--great] > pivot2);
+
             /*
              * Partitioning:
              *
-             *   left part         center part                    right part
-             * +------------------------------------------------------------+
-             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
-             * +------------------------------------------------------------+
-             *              ^                          ^       ^
-             *              |                          |       |
-             *             less                        k     great
+             *   left part           center part                   right part
+             * +--------------------------------------------------------------+
+             * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
+             * +--------------------------------------------------------------+
+             *               ^                          ^       ^
+             *               |                          |       |
+             *              less                        k     great
              *
              * Invariants:
              *
@@ -1060,16 +1298,14 @@
              *    pivot1 <= all in [less, k)     <= pivot2
              *              all in (great, right) > pivot2
              *
-             * Pointer k is the first index of ?-part
+             * Pointer k is the first index of ?-part.
              */
             outer:
             for (int k = less; k <= great; k++) {
                 char ak = a[k];
                 if (ak < pivot1) { // Move a[k] to left part
-                    if (k != less) {
-                        a[k] = a[less];
-                        a[less] = ak;
-                    }
+                    a[k] = a[less];
+                    a[less] = ak;
                     less++;
                 } else if (ak > pivot2) { // Move a[k] to right part
                     while (a[great] > pivot2) {
@@ -1079,26 +1315,107 @@
                     }
                     if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = a[great];
-                        a[great--] = ak;
+                        a[less] = a[great];
+                        less++;
                     } else { // pivot1 <= a[great] <= pivot2
                         a[k] = a[great];
-                        a[great--] = ak;
+                    }
+                    a[great] = ak;
+                    great--;
+                }
+            }
+
+            // Swap pivots into their final positions
+            a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
+            a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+            // Sort left and right parts recursively, excluding known pivots
+            sort(a, left, less - 2, leftmost);
+            sort(a, great + 2, right, false);
+
+            /*
+             * If center part is too large (comprises > 5/7 of the array),
+             * swap internal pivot values to ends.
+             */
+            if (less < e1 && e5 < great) {
+                /*
+                 * Skip elements, which are equal to pivot values.
+                 */
+                while (a[less] == pivot1) {
+                    less++;
+                }
+                while (a[great] == pivot2) {
+                    great--;
+                }
+
+                /*
+                 * Partitioning:
+                 *
+                 *   left part         center part                  right part
+                 * +----------------------------------------------------------+
+                 * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
+                 * +----------------------------------------------------------+
+                 *              ^                        ^       ^
+                 *              |                        |       |
+                 *             less                      k     great
+                 *
+                 * Invariants:
+                 *
+                 *              all in (*,  less) == pivot1
+                 *     pivot1 < all in [less,  k)  < pivot2
+                 *              all in (great, *) == pivot2
+                 *
+                 * Pointer k is the first index of ?-part.
+                 */
+                outer:
+                for (int k = less; k <= great; k++) {
+                    char ak = a[k];
+                    if (ak == pivot1) { // Move a[k] to left part
+                        a[k] = a[less];
+                        a[less] = ak;
+                        less++;
+                    } else if (ak == pivot2) { // Move a[k] to right part
+                        while (a[great] == pivot2) {
+                            if (great-- == k) {
+                                break outer;
+                            }
+                        }
+                        if (a[great] == pivot1) {
+                            a[k] = a[less];
+                            /*
+                             * Even though a[great] equals to pivot1, the
+                             * assignment a[less] = pivot1 may be incorrect,
+                             * if a[great] and pivot1 are floating-point zeros
+                             * of different signs. Therefore in float and
+                             * double sorting methods we have to use more
+                             * accurate assignment a[less] = a[great].
+                             */
+                            a[less] = pivot1;
+                            less++;
+                        } else { // pivot1 < a[great] < pivot2
+                            a[k] = a[great];
+                        }
+                        a[great] = ak;
+                        great--;
                     }
                 }
             }
+
+            // Sort center part recursively
+            sort(a, less, great, false);
+
         } else { // Pivots are equal
             /*
-             * Partition degenerates to the traditional 3-way,
-             * or "Dutch National Flag", partition:
+             * Partition degenerates to the traditional 3-way
+             * (or "Dutch National Flag") schema:
              *
-             *   left part   center part            right part
-             * +----------------------------------------------+
-             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
-             * +----------------------------------------------+
-             *              ^            ^       ^
-             *              |            |       |
-             *             less          k     great
+             *   left part    center part              right part
+             * +-------------------------------------------------+
+             * |  < pivot  |   == pivot   |     ?    |  > pivot  |
+             * +-------------------------------------------------+
+             *              ^              ^        ^
+             *              |              |        |
+             *             less            k      great
              *
              * Invariants:
              *
@@ -1106,20 +1423,19 @@
              *   all in [less, k)     == pivot
              *   all in (great, right) > pivot
              *
-             * Pointer k is the first index of ?-part
+             * Pointer k is the first index of ?-part.
              */
-            for (int k = less; k <= great; k++) {
-                char ak = a[k];
-                if (ak == pivot1) {
+            for (int k = left; k <= great; k++) {
+                if (a[k] == pivot1) {
                     continue;
                 }
+                char ak = a[k];
+
                 if (ak < pivot1) { // Move a[k] to left part
-                    if (k != less) {
-                        a[k] = a[less];
-                        a[less] = ak;
-                    }
+                    a[k] = a[less];
+                    a[less] = ak;
                     less++;
-                } else { // (a[k] > pivot1) - Move a[k] to right part
+                } else { // a[k] > pivot1 - Move a[k] to right part
                     /*
                      * We know that pivot1 == a[e3] == pivot2. Thus, we know
                      * that great will still be >= k when the following loop
@@ -1127,92 +1443,33 @@
                      * In other words, a[e3] acts as a sentinel for great.
                      */
                     while (a[great] > pivot1) {
+                        // assert great > k;
                         great--;
                     }
                     if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = a[great];
-                        a[great--] = ak;
+                        a[less] = a[great];
+                        less++;
                     } else { // a[great] == pivot1
+                        /*
+                         * Even though a[great] equals to pivot1, the
+                         * assignment a[k] = pivot1 may be incorrect,
+                         * if a[great] and pivot1 are floating-point
+                         * zeros of different signs. Therefore in float
+                         * and double sorting methods we have to use
+                         * more accurate assignment a[k] = a[great].
+                         */
                         a[k] = pivot1;
-                        a[great--] = ak;
                     }
+                    a[great] = ak;
+                    great--;
                 }
             }
+
+            // Sort left and right parts recursively
+            sort(a, left, less - 1, leftmost);
+            sort(a, great + 1, right, false);
         }
-
-        // Swap pivots into their final positions
-        a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
-        a[right] = a[great + 1]; a[great + 1] = pivot2;
-
-        // Sort left and right parts recursively, excluding known pivot values
-        doSort(a, left,   less - 2);
-        doSort(a, great + 2, right);
-
-        /*
-         * If pivot1 == pivot2, all elements from center
-         * part are equal and, therefore, already sorted
-         */
-        if (!pivotsDiffer) {
-            return;
-        }
-
-        /*
-         * If center part is too large (comprises > 2/3 of the array),
-         * swap internal pivot values to ends
-         */
-        if (less < e1 && great > e5) {
-            while (a[less] == pivot1) {
-                less++;
-            }
-            while (a[great] == pivot2) {
-                great--;
-            }
-
-            /*
-             * Partitioning:
-             *
-             *   left part       center part                   right part
-             * +----------------------------------------------------------+
-             * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
-             * +----------------------------------------------------------+
-             *              ^                        ^       ^
-             *              |                        |       |
-             *             less                      k     great
-             *
-             * Invariants:
-             *
-             *              all in (*, less)  == pivot1
-             *     pivot1 < all in [less, k)   < pivot2
-             *              all in (great, *) == pivot2
-             *
-             * Pointer k is the first index of ?-part
-             */
-            outer:
-            for (int k = less; k <= great; k++) {
-                char ak = a[k];
-                if (ak == pivot2) { // Move a[k] to right part
-                    while (a[great] == pivot2) {
-                        if (great-- == k) {
-                            break outer;
-                        }
-                    }
-                    if (a[great] == pivot1) {
-                        a[k] = a[less];
-                        a[less++] = pivot1;
-                    } else { // pivot1 < a[great] < pivot2
-                        a[k] = a[great];
-                    }
-                    a[great--] = pivot2;
-                } else if (ak == pivot1) { // Move a[k] to left part
-                    a[k] = a[less];
-                    a[less++] = pivot1;
-                }
-            }
-        }
-
-        // Sort center part recursively, excluding known pivot values
-        doSort(a, less, great);
     }
 
     /**
@@ -1221,7 +1478,11 @@
      * @param a the array to be sorted
      */
     public static void sort(byte[] a) {
-        doSort(a, 0, a.length - 1);
+        if (a.length > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
+            countingSort(a, 0, a.length - 1);
+        } else {
+            sort(a, 0, a.length - 1, true);
+        }
     }
 
     /**
@@ -1239,115 +1500,166 @@
      */
     public static void sort(byte[] a, int fromIndex, int toIndex) {
         rangeCheck(a.length, fromIndex, toIndex);
-        doSort(a, fromIndex, toIndex - 1);
+
+        if (toIndex - fromIndex > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
+            countingSort(a, fromIndex, toIndex - 1);
+        } else {
+            sort(a, fromIndex, toIndex - 1, true);
+        }
     }
 
     /** The number of distinct byte values. */
     private static final int NUM_BYTE_VALUES = 1 << 8;
 
     /**
-     * Sorts the specified range of the array into ascending order. This
-     * method differs from the public {@code sort} method in that the
-     * {@code right} index is inclusive, and it does no range checking on
-     * {@code left} or {@code right}.
+     * Sorts the specified range of the array by counting sort.
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
      */
-    private static void doSort(byte[] a, int left, int right) {
-        // Use insertion sort on tiny arrays
-        if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
-            for (int i = left + 1; i <= right; i++) {
-                byte ai = a[i];
-                int j;
-                for (j = i - 1; j >= left && ai < a[j]; j--) {
-                    a[j + 1] = a[j];
-                }
-                a[j + 1] = ai;
+    private static void countingSort(byte[] a, int left, int right) {
+        int[] count = new int[NUM_BYTE_VALUES];
+
+        for (int i = left; i <= right; i++) {
+            count[a[i] - Byte.MIN_VALUE]++;
+        }
+        for (int i = NUM_BYTE_VALUES - 1, k = right; k >= left; i--) {
+            while (count[i] == 0) {
+                i--;
             }
-        } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
-            // Use counting sort on huge arrays
-            int[] count = new int[NUM_BYTE_VALUES];
+            byte value = (byte) (i + Byte.MIN_VALUE);
+            int s = count[i];
 
-            for (int i = left; i <= right; i++) {
-                count[a[i] - Byte.MIN_VALUE]++;
-            }
-            for (int i = 0, k = left; i < count.length && k <= right; i++) {
-                byte value = (byte) (i + Byte.MIN_VALUE);
-
-                for (int s = count[i]; s > 0; s--) {
-                    a[k++] = value;
-               }
-            }
-        } else { // Use Dual-Pivot Quicksort on large arrays
-            dualPivotQuicksort(a, left, right);
+            do {
+                a[k--] = value;
+            } while (--s > 0);
         }
     }
 
     /**
      * Sorts the specified range of the array into ascending order by the
-     * Dual-Pivot Quicksort algorithm.
+     * Dual-Pivot Quicksort algorithm. This method differs from the public
+     * {@code sort} method in that the {@code right} index is inclusive,
+     * it does no range checking on {@code left} or {@code right}, and has
+     * boolean flag whether insertion sort with sentinel is used or not.
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param leftmost indicates if the part is the most left in the range
      */
-    private static void dualPivotQuicksort(byte[] a, int left, int right) {
-        // Compute indices of five evenly spaced elements
-        int sixth = (right - left + 1) / 6;
-        int e1 = left  + sixth;
-        int e5 = right - sixth;
+    private static void sort(byte[] a, int left, int right, boolean leftmost) {
+        int length = right - left + 1;
+
+        // Use insertion sort on tiny arrays
+        if (length < INSERTION_SORT_THRESHOLD) {
+            if (!leftmost) {
+                /*
+                 * Every element in adjoining part plays the role
+                 * of sentinel, therefore this allows us to avoid
+                 * the j >= left check on each iteration.
+                 */
+                for (int j, i = left + 1; i <= right; i++) {
+                    byte ai = a[i];
+                    for (j = i - 1; ai < a[j]; j--) {
+                        // assert j >= left;
+                        a[j + 1] = a[j];
+                    }
+                    a[j + 1] = ai;
+                }
+            } else {
+                /*
+                 * For case of leftmost part traditional (without a sentinel)
+                 * insertion sort, optimized for server JVM, is used.
+                 */
+                for (int i = left, j = i; i < right; j = ++i) {
+                    byte ai = a[i + 1];
+                    while (ai < a[j]) {
+                        a[j + 1] = a[j];
+                        if (j-- == left) {
+                            break;
+                        }
+                    }
+                    a[j + 1] = ai;
+                }
+            }
+            return;
+        }
+
+        // Inexpensive approximation of length / 7
+        int seventh = (length >>> 3) + (length >>> 6) + 1;
+
+        /*
+         * Sort five evenly spaced elements around (and including) the
+         * center element in the range. These elements will be used for
+         * pivot selection as described below. The choice for spacing
+         * these elements was empirically determined to work well on
+         * a wide variety of inputs.
+         */
         int e3 = (left + right) >>> 1; // The midpoint
-        int e4 = e3 + sixth;
-        int e2 = e3 - sixth;
+        int e2 = e3 - seventh;
+        int e1 = e2 - seventh;
+        int e4 = e3 + seventh;
+        int e5 = e4 + seventh;
 
-        // Sort these elements using a 5-element sorting network
-        byte ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+        // Sort these elements using insertion sort
+        if (a[e2] < a[e1]) { byte t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
 
-        if (ae1 > ae2) { byte t = ae1; ae1 = ae2; ae2 = t; }
-        if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; }
-        if (ae1 > ae3) { byte t = ae1; ae1 = ae3; ae3 = t; }
-        if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; }
-        if (ae1 > ae4) { byte t = ae1; ae1 = ae4; ae4 = t; }
-        if (ae3 > ae4) { byte t = ae3; ae3 = ae4; ae4 = t; }
-        if (ae2 > ae5) { byte t = ae2; ae2 = ae5; ae5 = t; }
-        if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; }
-        if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; }
-
-        a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+        if (a[e3] < a[e2]) { byte t = a[e3]; a[e3] = a[e2]; a[e2] = t;
+            if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+        }
+        if (a[e4] < a[e3]) { byte t = a[e4]; a[e4] = a[e3]; a[e3] = t;
+            if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+                if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+            }
+        }
+        if (a[e5] < a[e4]) { byte t = a[e5]; a[e5] = a[e4]; a[e4] = t;
+            if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
+                if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+                    if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+                }
+            }
+        }
 
         /*
          * Use the second and fourth of the five sorted elements as pivots.
          * These values are inexpensive approximations of the first and
          * second terciles of the array. Note that pivot1 <= pivot2.
-         *
-         * The pivots are stored in local variables, and the first and
-         * the last of the elements to be sorted are moved to the locations
-         * formerly occupied by the pivots. When partitioning is complete,
-         * the pivots are swapped back into their final positions, and
-         * excluded from subsequent sorting.
          */
-        byte pivot1 = ae2; a[e2] = a[left];
-        byte pivot2 = ae4; a[e4] = a[right];
+        byte pivot1 = a[e2];
+        byte pivot2 = a[e4];
 
         // Pointers
-        int less  = left  + 1; // The index of first element of center part
-        int great = right - 1; // The index before first element of right part
+        int less  = left;  // The index of the first element of center part
+        int great = right; // The index before the first element of right part
 
-        boolean pivotsDiffer = (pivot1 != pivot2);
+        if (pivot1 != pivot2) {
+            /*
+             * The first and the last elements to be sorted are moved to the
+             * locations formerly occupied by the pivots. When partitioning
+             * is complete, the pivots are swapped back into their final
+             * positions, and excluded from subsequent sorting.
+             */
+            a[e2] = a[left];
+            a[e4] = a[right];
 
-        if (pivotsDiffer) {
+            /*
+             * Skip elements, which are less or greater than pivot values.
+             */
+            while (a[++less] < pivot1);
+            while (a[--great] > pivot2);
+
             /*
              * Partitioning:
              *
-             *   left part         center part                    right part
-             * +------------------------------------------------------------+
-             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
-             * +------------------------------------------------------------+
-             *              ^                          ^       ^
-             *              |                          |       |
-             *             less                        k     great
+             *   left part           center part                   right part
+             * +--------------------------------------------------------------+
+             * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
+             * +--------------------------------------------------------------+
+             *               ^                          ^       ^
+             *               |                          |       |
+             *              less                        k     great
              *
              * Invariants:
              *
@@ -1355,16 +1667,14 @@
              *    pivot1 <= all in [less, k)     <= pivot2
              *              all in (great, right) > pivot2
              *
-             * Pointer k is the first index of ?-part
+             * Pointer k is the first index of ?-part.
              */
             outer:
             for (int k = less; k <= great; k++) {
                 byte ak = a[k];
                 if (ak < pivot1) { // Move a[k] to left part
-                    if (k != less) {
-                        a[k] = a[less];
-                        a[less] = ak;
-                    }
+                    a[k] = a[less];
+                    a[less] = ak;
                     less++;
                 } else if (ak > pivot2) { // Move a[k] to right part
                     while (a[great] > pivot2) {
@@ -1374,26 +1684,107 @@
                     }
                     if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = a[great];
-                        a[great--] = ak;
+                        a[less] = a[great];
+                        less++;
                     } else { // pivot1 <= a[great] <= pivot2
                         a[k] = a[great];
-                        a[great--] = ak;
+                    }
+                    a[great] = ak;
+                    great--;
+                }
+            }
+
+            // Swap pivots into their final positions
+            a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
+            a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+            // Sort left and right parts recursively, excluding known pivots
+            sort(a, left, less - 2, leftmost);
+            sort(a, great + 2, right, false);
+
+            /*
+             * If center part is too large (comprises > 5/7 of the array),
+             * swap internal pivot values to ends.
+             */
+            if (less < e1 && e5 < great) {
+                /*
+                 * Skip elements, which are equal to pivot values.
+                 */
+                while (a[less] == pivot1) {
+                    less++;
+                }
+                while (a[great] == pivot2) {
+                    great--;
+                }
+
+                /*
+                 * Partitioning:
+                 *
+                 *   left part         center part                  right part
+                 * +----------------------------------------------------------+
+                 * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
+                 * +----------------------------------------------------------+
+                 *              ^                        ^       ^
+                 *              |                        |       |
+                 *             less                      k     great
+                 *
+                 * Invariants:
+                 *
+                 *              all in (*,  less) == pivot1
+                 *     pivot1 < all in [less,  k)  < pivot2
+                 *              all in (great, *) == pivot2
+                 *
+                 * Pointer k is the first index of ?-part.
+                 */
+                outer:
+                for (int k = less; k <= great; k++) {
+                    byte ak = a[k];
+                    if (ak == pivot1) { // Move a[k] to left part
+                        a[k] = a[less];
+                        a[less] = ak;
+                        less++;
+                    } else if (ak == pivot2) { // Move a[k] to right part
+                        while (a[great] == pivot2) {
+                            if (great-- == k) {
+                                break outer;
+                            }
+                        }
+                        if (a[great] == pivot1) {
+                            a[k] = a[less];
+                            /*
+                             * Even though a[great] equals to pivot1, the
+                             * assignment a[less] = pivot1 may be incorrect,
+                             * if a[great] and pivot1 are floating-point zeros
+                             * of different signs. Therefore in float and
+                             * double sorting methods we have to use more
+                             * accurate assignment a[less] = a[great].
+                             */
+                            a[less] = pivot1;
+                            less++;
+                        } else { // pivot1 < a[great] < pivot2
+                            a[k] = a[great];
+                        }
+                        a[great] = ak;
+                        great--;
                     }
                 }
             }
+
+            // Sort center part recursively
+            sort(a, less, great, false);
+
         } else { // Pivots are equal
             /*
-             * Partition degenerates to the traditional 3-way,
-             * or "Dutch National Flag", partition:
+             * Partition degenerates to the traditional 3-way
+             * (or "Dutch National Flag") schema:
              *
-             *   left part   center part            right part
-             * +----------------------------------------------+
-             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
-             * +----------------------------------------------+
-             *              ^            ^       ^
-             *              |            |       |
-             *             less          k     great
+             *   left part    center part              right part
+             * +-------------------------------------------------+
+             * |  < pivot  |   == pivot   |     ?    |  > pivot  |
+             * +-------------------------------------------------+
+             *              ^              ^        ^
+             *              |              |        |
+             *             less            k      great
              *
              * Invariants:
              *
@@ -1401,20 +1792,19 @@
              *   all in [less, k)     == pivot
              *   all in (great, right) > pivot
              *
-             * Pointer k is the first index of ?-part
+             * Pointer k is the first index of ?-part.
              */
-            for (int k = less; k <= great; k++) {
-                byte ak = a[k];
-                if (ak == pivot1) {
+            for (int k = left; k <= great; k++) {
+                if (a[k] == pivot1) {
                     continue;
                 }
+                byte ak = a[k];
+
                 if (ak < pivot1) { // Move a[k] to left part
-                    if (k != less) {
-                        a[k] = a[less];
-                        a[less] = ak;
-                    }
+                    a[k] = a[less];
+                    a[less] = ak;
                     less++;
-                } else { // (a[k] > pivot1) - Move a[k] to right part
+                } else { // a[k] > pivot1 - Move a[k] to right part
                     /*
                      * We know that pivot1 == a[e3] == pivot2. Thus, we know
                      * that great will still be >= k when the following loop
@@ -1422,92 +1812,33 @@
                      * In other words, a[e3] acts as a sentinel for great.
                      */
                     while (a[great] > pivot1) {
+                        // assert great > k;
                         great--;
                     }
                     if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = a[great];
-                        a[great--] = ak;
+                        a[less] = a[great];
+                        less++;
                     } else { // a[great] == pivot1
+                        /*
+                         * Even though a[great] equals to pivot1, the
+                         * assignment a[k] = pivot1 may be incorrect,
+                         * if a[great] and pivot1 are floating-point
+                         * zeros of different signs. Therefore in float
+                         * and double sorting methods we have to use
+                         * more accurate assignment a[k] = a[great].
+                         */
                         a[k] = pivot1;
-                        a[great--] = ak;
                     }
+                    a[great] = ak;
+                    great--;
                 }
             }
+
+            // Sort left and right parts recursively
+            sort(a, left, less - 1, leftmost);
+            sort(a, great + 1, right, false);
         }
-
-        // Swap pivots into their final positions
-        a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
-        a[right] = a[great + 1]; a[great + 1] = pivot2;
-
-        // Sort left and right parts recursively, excluding known pivot values
-        doSort(a, left,   less - 2);
-        doSort(a, great + 2, right);
-
-        /*
-         * If pivot1 == pivot2, all elements from center
-         * part are equal and, therefore, already sorted
-         */
-        if (!pivotsDiffer) {
-            return;
-        }
-
-        /*
-         * If center part is too large (comprises > 2/3 of the array),
-         * swap internal pivot values to ends
-         */
-        if (less < e1 && great > e5) {
-            while (a[less] == pivot1) {
-                less++;
-            }
-            while (a[great] == pivot2) {
-                great--;
-            }
-
-            /*
-             * Partitioning:
-             *
-             *   left part       center part                   right part
-             * +----------------------------------------------------------+
-             * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
-             * +----------------------------------------------------------+
-             *              ^                        ^       ^
-             *              |                        |       |
-             *             less                      k     great
-             *
-             * Invariants:
-             *
-             *              all in (*, less)  == pivot1
-             *     pivot1 < all in [less, k)   < pivot2
-             *              all in (great, *) == pivot2
-             *
-             * Pointer k is the first index of ?-part
-             */
-            outer:
-            for (int k = less; k <= great; k++) {
-                byte ak = a[k];
-                if (ak == pivot2) { // Move a[k] to right part
-                    while (a[great] == pivot2) {
-                        if (great-- == k) {
-                            break outer;
-                        }
-                    }
-                    if (a[great] == pivot1) {
-                        a[k] = a[less];
-                        a[less++] = pivot1;
-                    } else { // pivot1 < a[great] < pivot2
-                        a[k] = a[great];
-                    }
-                    a[great--] = pivot2;
-                } else if (ak == pivot1) { // Move a[k] to left part
-                    a[k] = a[less];
-                    a[less++] = pivot1;
-                }
-            }
-        }
-
-        // Sort center part recursively, excluding known pivot values
-        doSort(a, less, great);
     }
 
     /**
@@ -1531,7 +1862,7 @@
      * Sorts the specified range of the array into ascending order. The range
      * to be sorted extends from the index {@code fromIndex}, inclusive, to
      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
-     * the range to be sorted is empty and the call is a no-op).
+     * the range to be sorted is empty (and the call is a no-op).
      *
      * <p>The {@code <} relation does not provide a total order on all float
      * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
@@ -1565,162 +1896,207 @@
      */
     private static void sortNegZeroAndNaN(float[] a, int left, int right) {
         /*
-         * Phase 1: Count negative zeros and move NaNs to end of array
+         * Phase 1: Move NaNs to the end of the array.
          */
-        final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
-        int numNegativeZeros = 0;
-        int n = right;
-
-        for (int k = left; k <= n; k++) {
+        while (left <= right && Float.isNaN(a[right])) {
+            right--;
+        }
+        for (int k = right - 1; k >= left; k--) {
             float ak = a[k];
-            if (ak == 0.0f && NEGATIVE_ZERO == Float.floatToIntBits(ak)) {
-                a[k] = 0.0f;
-                numNegativeZeros++;
-            } else if (ak != ak) { // i.e., ak is NaN
-                a[k--] = a[n];
-                a[n--] = Float.NaN;
+            if (ak != ak) { // a[k] is NaN
+                a[k] = a[right];
+                a[right] = ak;
+                right--;
             }
         }
 
         /*
-         * Phase 2: Sort everything except NaNs (which are already in place)
+         * Phase 2: Sort everything except NaNs (which are already in place).
          */
-        doSort(a, left, n);
+        sort(a, left, right, true);
 
         /*
-         * Phase 3: Turn positive zeros back into negative zeros as appropriate
+         * Phase 3: Place negative zeros before positive zeros.
          */
-        if (numNegativeZeros == 0) {
-            return;
-        }
+        int hi = right;
 
-        // Find first zero element
-        int zeroIndex = findAnyZero(a, left, n);
-
-        for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) {
-            zeroIndex = i;
-        }
-
-        // Turn the right number of positive zeros back into negative zeros
-        for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {
-            a[i] = -0.0f;
-        }
-    }
-
-    /**
-     * Returns the index of some zero element in the specified range via
-     * binary search. The range is assumed to be sorted, and must contain
-     * at least one zero.
-     *
-     * @param a the array to be searched
-     * @param low the index of the first element, inclusive, to be searched
-     * @param high the index of the last element, inclusive, to be searched
-     */
-    private static int findAnyZero(float[] a, int low, int high) {
-        while (true) {
-            int middle = (low + high) >>> 1;
+        /*
+         * Search first zero, or first positive, or last negative element.
+         */
+        while (left < hi) {
+            int middle = (left + hi) >>> 1;
             float middleValue = a[middle];
 
             if (middleValue < 0.0f) {
-                low = middle + 1;
-            } else if (middleValue > 0.0f) {
-                high = middle - 1;
-            } else { // middleValue == 0.0f
-                return middle;
+                left = middle + 1;
+            } else {
+                hi = middle;
+            }
+        }
+
+        /*
+         * Skip the last negative value (if any) or all leading negative zeros.
+         */
+        while (left <= right && Float.floatToRawIntBits(a[left]) < 0) {
+            left++;
+        }
+
+        /*
+         * Move negative zeros to the beginning of the sub-range.
+         *
+         * Partitioning:
+         *
+         * +---------------------------------------------------+
+         * |   < 0.0   |   -0.0   |    0.0    |  ?  ( >= 0.0 ) |
+         * +---------------------------------------------------+
+         *              ^          ^           ^
+         *              |          |           |
+         *             left        p           k
+         *
+         * Invariants:
+         *
+         *   all in (*,  left)  <  0.0
+         *   all in [left,  p) == -0.0
+         *   all in [p,     k) ==  0.0
+         *   all in [k, right] >=  0.0
+         *
+         * Pointer k is the first index of ?-part.
+         */
+        for (int k = left + 1, p = left; k <= right; k++) {
+            float ak = a[k];
+            if (ak != 0.0f) {
+                break;
+            }
+            if (Float.floatToRawIntBits(ak) < 0) { // ak is -0.0f
+                a[k] = 0.0f;
+                a[p++] = -0.0f;
             }
         }
     }
 
     /**
-     * Sorts the specified range of the array into ascending order. This
-     * method differs from the public {@code sort} method in three ways:
-     * {@code right} index is inclusive, it does no range checking on
-     * {@code left} or {@code right}, and it does not handle negative
-     * zeros or NaNs in the array.
-     *
-     * @param a the array to be sorted, which must not contain -0.0f or NaN
-     * @param left the index of the first element, inclusive, to be sorted
-     * @param right the index of the last element, inclusive, to be sorted
-     */
-    private static void doSort(float[] a, int left, int right) {
-        // Use insertion sort on tiny arrays
-        if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
-            for (int i = left + 1; i <= right; i++) {
-                float ai = a[i];
-                int j;
-                for (j = i - 1; j >= left && ai < a[j]; j--) {
-                    a[j + 1] = a[j];
-                }
-                a[j + 1] = ai;
-            }
-        } else { // Use Dual-Pivot Quicksort on large arrays
-            dualPivotQuicksort(a, left, right);
-        }
-    }
-
-    /**
      * Sorts the specified range of the array into ascending order by the
-     * Dual-Pivot Quicksort algorithm.
+     * Dual-Pivot Quicksort algorithm. This method differs from the public
+     * {@code sort} method in that the {@code right} index is inclusive,
+     * it does no range checking on {@code left} or {@code right}, and has
+     * boolean flag whether insertion sort with sentinel is used or not.
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param leftmost indicates if the part is the most left in the range
      */
-    private static void dualPivotQuicksort(float[] a, int left, int right) {
-        // Compute indices of five evenly spaced elements
-        int sixth = (right - left + 1) / 6;
-        int e1 = left  + sixth;
-        int e5 = right - sixth;
+    private static void sort(float[] a, int left, int right,boolean leftmost) {
+        int length = right - left + 1;
+
+        // Use insertion sort on tiny arrays
+        if (length < INSERTION_SORT_THRESHOLD) {
+            if (!leftmost) {
+                /*
+                 * Every element in adjoining part plays the role
+                 * of sentinel, therefore this allows us to avoid
+                 * the j >= left check on each iteration.
+                 */
+                for (int j, i = left + 1; i <= right; i++) {
+                    float ai = a[i];
+                    for (j = i - 1; ai < a[j]; j--) {
+                        // assert j >= left;
+                        a[j + 1] = a[j];
+                    }
+                    a[j + 1] = ai;
+                }
+            } else {
+                /*
+                 * For case of leftmost part traditional (without a sentinel)
+                 * insertion sort, optimized for server JVM, is used.
+                 */
+                for (int i = left, j = i; i < right; j = ++i) {
+                    float ai = a[i + 1];
+                    while (ai < a[j]) {
+                        a[j + 1] = a[j];
+                        if (j-- == left) {
+                            break;
+                        }
+                    }
+                    a[j + 1] = ai;
+                }
+            }
+            return;
+        }
+
+        // Inexpensive approximation of length / 7
+        int seventh = (length >>> 3) + (length >>> 6) + 1;
+
+        /*
+         * Sort five evenly spaced elements around (and including) the
+         * center element in the range. These elements will be used for
+         * pivot selection as described below. The choice for spacing
+         * these elements was empirically determined to work well on
+         * a wide variety of inputs.
+         */
         int e3 = (left + right) >>> 1; // The midpoint
-        int e4 = e3 + sixth;
-        int e2 = e3 - sixth;
+        int e2 = e3 - seventh;
+        int e1 = e2 - seventh;
+        int e4 = e3 + seventh;
+        int e5 = e4 + seventh;
 
-        // Sort these elements using a 5-element sorting network
-        float ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+        // Sort these elements using insertion sort
+        if (a[e2] < a[e1]) { float t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
 
-        if (ae1 > ae2) { float t = ae1; ae1 = ae2; ae2 = t; }
-        if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; }
-        if (ae1 > ae3) { float t = ae1; ae1 = ae3; ae3 = t; }
-        if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; }
-        if (ae1 > ae4) { float t = ae1; ae1 = ae4; ae4 = t; }
-        if (ae3 > ae4) { float t = ae3; ae3 = ae4; ae4 = t; }
-        if (ae2 > ae5) { float t = ae2; ae2 = ae5; ae5 = t; }
-        if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; }
-        if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; }
-
-        a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+        if (a[e3] < a[e2]) { float t = a[e3]; a[e3] = a[e2]; a[e2] = t;
+            if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+        }
+        if (a[e4] < a[e3]) { float t = a[e4]; a[e4] = a[e3]; a[e3] = t;
+            if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+                if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+            }
+        }
+        if (a[e5] < a[e4]) { float t = a[e5]; a[e5] = a[e4]; a[e4] = t;
+            if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
+                if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+                    if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+                }
+            }
+        }
 
         /*
          * Use the second and fourth of the five sorted elements as pivots.
          * These values are inexpensive approximations of the first and
          * second terciles of the array. Note that pivot1 <= pivot2.
-         *
-         * The pivots are stored in local variables, and the first and
-         * the last of the elements to be sorted are moved to the locations
-         * formerly occupied by the pivots. When partitioning is complete,
-         * the pivots are swapped back into their final positions, and
-         * excluded from subsequent sorting.
          */
-        float pivot1 = ae2; a[e2] = a[left];
-        float pivot2 = ae4; a[e4] = a[right];
+        float pivot1 = a[e2];
+        float pivot2 = a[e4];
 
         // Pointers
-        int less  = left  + 1; // The index of first element of center part
-        int great = right - 1; // The index before first element of right part
+        int less  = left;  // The index of the first element of center part
+        int great = right; // The index before the first element of right part
 
-        boolean pivotsDiffer = (pivot1 != pivot2);
+        if (pivot1 != pivot2) {
+            /*
+             * The first and the last elements to be sorted are moved to the
+             * locations formerly occupied by the pivots. When partitioning
+             * is complete, the pivots are swapped back into their final
+             * positions, and excluded from subsequent sorting.
+             */
+            a[e2] = a[left];
+            a[e4] = a[right];
 
-        if (pivotsDiffer) {
+            /*
+             * Skip elements, which are less or greater than pivot values.
+             */
+            while (a[++less] < pivot1);
+            while (a[--great] > pivot2);
+
             /*
              * Partitioning:
              *
-             *   left part         center part                    right part
-             * +------------------------------------------------------------+
-             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
-             * +------------------------------------------------------------+
-             *              ^                          ^       ^
-             *              |                          |       |
-             *             less                        k     great
+             *   left part           center part                   right part
+             * +--------------------------------------------------------------+
+             * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
+             * +--------------------------------------------------------------+
+             *               ^                          ^       ^
+             *               |                          |       |
+             *              less                        k     great
              *
              * Invariants:
              *
@@ -1728,16 +2104,14 @@
              *    pivot1 <= all in [less, k)     <= pivot2
              *              all in (great, right) > pivot2
              *
-             * Pointer k is the first index of ?-part
+             * Pointer k is the first index of ?-part.
              */
             outer:
             for (int k = less; k <= great; k++) {
                 float ak = a[k];
                 if (ak < pivot1) { // Move a[k] to left part
-                    if (k != less) {
-                        a[k] = a[less];
-                        a[less] = ak;
-                    }
+                    a[k] = a[less];
+                    a[less] = ak;
                     less++;
                 } else if (ak > pivot2) { // Move a[k] to right part
                     while (a[great] > pivot2) {
@@ -1747,26 +2121,107 @@
                     }
                     if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = a[great];
-                        a[great--] = ak;
+                        a[less] = a[great];
+                        less++;
                     } else { // pivot1 <= a[great] <= pivot2
                         a[k] = a[great];
-                        a[great--] = ak;
+                    }
+                    a[great] = ak;
+                    great--;
+                }
+            }
+
+            // Swap pivots into their final positions
+            a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
+            a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+            // Sort left and right parts recursively, excluding known pivots
+            sort(a, left, less - 2, leftmost);
+            sort(a, great + 2, right, false);
+
+            /*
+             * If center part is too large (comprises > 5/7 of the array),
+             * swap internal pivot values to ends.
+             */
+            if (less < e1 && e5 < great) {
+                /*
+                 * Skip elements, which are equal to pivot values.
+                 */
+                while (a[less] == pivot1) {
+                    less++;
+                }
+                while (a[great] == pivot2) {
+                    great--;
+                }
+
+                /*
+                 * Partitioning:
+                 *
+                 *   left part         center part                  right part
+                 * +----------------------------------------------------------+
+                 * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
+                 * +----------------------------------------------------------+
+                 *              ^                        ^       ^
+                 *              |                        |       |
+                 *             less                      k     great
+                 *
+                 * Invariants:
+                 *
+                 *              all in (*,  less) == pivot1
+                 *     pivot1 < all in [less,  k)  < pivot2
+                 *              all in (great, *) == pivot2
+                 *
+                 * Pointer k is the first index of ?-part.
+                 */
+                outer:
+                for (int k = less; k <= great; k++) {
+                    float ak = a[k];
+                    if (ak == pivot1) { // Move a[k] to left part
+                        a[k] = a[less];
+                        a[less] = ak;
+                        less++;
+                    } else if (ak == pivot2) { // Move a[k] to right part
+                        while (a[great] == pivot2) {
+                            if (great-- == k) {
+                                break outer;
+                            }
+                        }
+                        if (a[great] == pivot1) {
+                            a[k] = a[less];
+                            /*
+                             * Even though a[great] equals to pivot1, the
+                             * assignment a[less] = pivot1 may be incorrect,
+                             * if a[great] and pivot1 are floating-point zeros
+                             * of different signs. Therefore in float and
+                             * double sorting methods we have to use more
+                             * accurate assignment a[less] = a[great].
+                             */
+                            a[less] = a[great];
+                            less++;
+                        } else { // pivot1 < a[great] < pivot2
+                            a[k] = a[great];
+                        }
+                        a[great] = ak;
+                        great--;
                     }
                 }
             }
+
+            // Sort center part recursively
+            sort(a, less, great, false);
+
         } else { // Pivots are equal
             /*
-             * Partition degenerates to the traditional 3-way,
-             * or "Dutch National Flag", partition:
+             * Partition degenerates to the traditional 3-way
+             * (or "Dutch National Flag") schema:
              *
-             *   left part   center part            right part
-             * +----------------------------------------------+
-             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
-             * +----------------------------------------------+
-             *              ^            ^       ^
-             *              |            |       |
-             *             less          k     great
+             *   left part    center part              right part
+             * +-------------------------------------------------+
+             * |  < pivot  |   == pivot   |     ?    |  > pivot  |
+             * +-------------------------------------------------+
+             *              ^              ^        ^
+             *              |              |        |
+             *             less            k      great
              *
              * Invariants:
              *
@@ -1774,20 +2229,19 @@
              *   all in [less, k)     == pivot
              *   all in (great, right) > pivot
              *
-             * Pointer k is the first index of ?-part
+             * Pointer k is the first index of ?-part.
              */
-            for (int k = less; k <= great; k++) {
-                float ak = a[k];
-                if (ak == pivot1) {
+            for (int k = left; k <= great; k++) {
+                if (a[k] == pivot1) {
                     continue;
                 }
+                float ak = a[k];
+
                 if (ak < pivot1) { // Move a[k] to left part
-                    if (k != less) {
-                        a[k] = a[less];
-                        a[less] = ak;
-                    }
+                    a[k] = a[less];
+                    a[less] = ak;
                     less++;
-                } else { // (a[k] > pivot1) - Move a[k] to right part
+                } else { // a[k] > pivot1 - Move a[k] to right part
                     /*
                      * We know that pivot1 == a[e3] == pivot2. Thus, we know
                      * that great will still be >= k when the following loop
@@ -1795,92 +2249,33 @@
                      * In other words, a[e3] acts as a sentinel for great.
                      */
                     while (a[great] > pivot1) {
+                        // assert great > k;
                         great--;
                     }
                     if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = a[great];
-                        a[great--] = ak;
+                        a[less] = a[great];
+                        less++;
                     } else { // a[great] == pivot1
-                        a[k] = pivot1;
-                        a[great--] = ak;
+                        /*
+                         * Even though a[great] equals to pivot1, the
+                         * assignment a[k] = pivot1 may be incorrect,
+                         * if a[great] and pivot1 are floating-point
+                         * zeros of different signs. Therefore in float
+                         * and double sorting methods we have to use
+                         * more accurate assignment a[k] = a[great].
+                         */
+                        a[k] = a[great];
                     }
+                    a[great] = ak;
+                    great--;
                 }
             }
+
+            // Sort left and right parts recursively
+            sort(a, left, less - 1, leftmost);
+            sort(a, great + 1, right, false);
         }
-
-        // Swap pivots into their final positions
-        a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
-        a[right] = a[great + 1]; a[great + 1] = pivot2;
-
-        // Sort left and right parts recursively, excluding known pivot values
-        doSort(a, left,   less - 2);
-        doSort(a, great + 2, right);
-
-        /*
-         * If pivot1 == pivot2, all elements from center
-         * part are equal and, therefore, already sorted
-         */
-        if (!pivotsDiffer) {
-            return;
-        }
-
-        /*
-         * If center part is too large (comprises > 2/3 of the array),
-         * swap internal pivot values to ends
-         */
-        if (less < e1 && great > e5) {
-            while (a[less] == pivot1) {
-                less++;
-            }
-            while (a[great] == pivot2) {
-                great--;
-            }
-
-            /*
-             * Partitioning:
-             *
-             *   left part       center part                   right part
-             * +----------------------------------------------------------+
-             * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
-             * +----------------------------------------------------------+
-             *              ^                        ^       ^
-             *              |                        |       |
-             *             less                      k     great
-             *
-             * Invariants:
-             *
-             *              all in (*, less)  == pivot1
-             *     pivot1 < all in [less, k)   < pivot2
-             *              all in (great, *) == pivot2
-             *
-             * Pointer k is the first index of ?-part
-             */
-            outer:
-            for (int k = less; k <= great; k++) {
-                float ak = a[k];
-                if (ak == pivot2) { // Move a[k] to right part
-                    while (a[great] == pivot2) {
-                        if (great-- == k) {
-                            break outer;
-                        }
-                    }
-                    if (a[great] == pivot1) {
-                        a[k] = a[less];
-                        a[less++] = pivot1;
-                    } else { // pivot1 < a[great] < pivot2
-                        a[k] = a[great];
-                    }
-                    a[great--] = pivot2;
-                } else if (ak == pivot1) { // Move a[k] to left part
-                    a[k] = a[less];
-                    a[less++] = pivot1;
-                }
-            }
-        }
-
-        // Sort center part recursively, excluding known pivot values
-        doSort(a, less, great);
     }
 
     /**
@@ -1938,162 +2333,207 @@
      */
     private static void sortNegZeroAndNaN(double[] a, int left, int right) {
         /*
-         * Phase 1: Count negative zeros and move NaNs to end of array
+         * Phase 1: Move NaNs to the end of the array.
          */
-        final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
-        int numNegativeZeros = 0;
-        int n = right;
-
-        for (int k = left; k <= n; k++) {
+        while (left <= right && Double.isNaN(a[right])) {
+            right--;
+        }
+        for (int k = right - 1; k >= left; k--) {
             double ak = a[k];
-            if (ak == 0.0d && NEGATIVE_ZERO == Double.doubleToLongBits(ak)) {
-                a[k] = 0.0d;
-                numNegativeZeros++;
-            } else if (ak != ak) { // i.e., ak is NaN
-                a[k--] = a[n];
-                a[n--] = Double.NaN;
+            if (ak != ak) { // a[k] is NaN
+                a[k] = a[right];
+                a[right] = ak;
+                right--;
             }
         }
 
         /*
-         * Phase 2: Sort everything except NaNs (which are already in place)
+         * Phase 2: Sort everything except NaNs (which are already in place).
          */
-        doSort(a, left, n);
+        sort(a, left, right, true);
 
         /*
-         * Phase 3: Turn positive zeros back into negative zeros as appropriate
+         * Phase 3: Place negative zeros before positive zeros.
          */
-        if (numNegativeZeros == 0) {
-            return;
-        }
+        int hi = right;
 
-        // Find first zero element
-        int zeroIndex = findAnyZero(a, left, n);
-
-        for (int i = zeroIndex - 1; i >= left && a[i] == 0.0d; i--) {
-            zeroIndex = i;
-        }
-
-        // Turn the right number of positive zeros back into negative zeros
-        for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {
-            a[i] = -0.0d;
-        }
-    }
-
-    /**
-     * Returns the index of some zero element in the specified range via
-     * binary search. The range is assumed to be sorted, and must contain
-     * at least one zero.
-     *
-     * @param a the array to be searched
-     * @param low the index of the first element, inclusive, to be searched
-     * @param high the index of the last element, inclusive, to be searched
-     */
-    private static int findAnyZero(double[] a, int low, int high) {
-        while (true) {
-            int middle = (low + high) >>> 1;
+        /*
+         * Search first zero, or first positive, or last negative element.
+         */
+        while (left < hi) {
+            int middle = (left + hi) >>> 1;
             double middleValue = a[middle];
 
             if (middleValue < 0.0d) {
-                low = middle + 1;
-            } else if (middleValue > 0.0d) {
-                high = middle - 1;
-            } else { // middleValue == 0.0d
-                return middle;
+                left = middle + 1;
+            } else {
+                hi = middle;
+            }
+        }
+
+        /*
+         * Skip the last negative value (if any) or all leading negative zeros.
+         */
+        while (left <= right && Double.doubleToRawLongBits(a[left]) < 0) {
+            left++;
+        }
+
+        /*
+         * Move negative zeros to the beginning of the sub-range.
+         *
+         * Partitioning:
+         *
+         * +---------------------------------------------------+
+         * |   < 0.0   |   -0.0   |    0.0    |  ?  ( >= 0.0 ) |
+         * +---------------------------------------------------+
+         *              ^          ^           ^
+         *              |          |           |
+         *             left        p           k
+         *
+         * Invariants:
+         *
+         *   all in (*,  left)  <  0.0
+         *   all in [left,  p) == -0.0
+         *   all in [p,     k) ==  0.0
+         *   all in [k, right] >=  0.0
+         *
+         * Pointer k is the first index of ?-part.
+         */
+        for (int k = left + 1, p = left; k <= right; k++) {
+            double ak = a[k];
+            if (ak != 0.0d) {
+                break;
+            }
+            if (Double.doubleToRawLongBits(ak) < 0) { // ak is -0.0d
+                a[k] = 0.0d;
+                a[p++] = -0.0d;
             }
         }
     }
 
     /**
-     * Sorts the specified range of the array into ascending order. This
-     * method differs from the public {@code sort} method in three ways:
-     * {@code right} index is inclusive, it does no range checking on
-     * {@code left} or {@code right}, and it does not handle negative
-     * zeros or NaNs in the array.
-     *
-     * @param a the array to be sorted, which must not contain -0.0d and NaN
-     * @param left the index of the first element, inclusive, to be sorted
-     * @param right the index of the last element, inclusive, to be sorted
-     */
-    private static void doSort(double[] a, int left, int right) {
-        // Use insertion sort on tiny arrays
-        if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
-            for (int i = left + 1; i <= right; i++) {
-                double ai = a[i];
-                int j;
-                for (j = i - 1; j >= left && ai < a[j]; j--) {
-                    a[j + 1] = a[j];
-                }
-                a[j + 1] = ai;
-            }
-        } else { // Use Dual-Pivot Quicksort on large arrays
-            dualPivotQuicksort(a, left, right);
-        }
-    }
-
-    /**
      * Sorts the specified range of the array into ascending order by the
-     * Dual-Pivot Quicksort algorithm.
+     * Dual-Pivot Quicksort algorithm. This method differs from the public
+     * {@code sort} method in that the {@code right} index is inclusive,
+     * it does no range checking on {@code left} or {@code right}, and has
+     * boolean flag whether insertion sort with sentinel is used or not.
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
      * @param right the index of the last element, inclusive, to be sorted
+     * @param leftmost indicates if the part is the most left in the range
      */
-    private static void dualPivotQuicksort(double[] a, int left, int right) {
-        // Compute indices of five evenly spaced elements
-        int sixth = (right - left + 1) / 6;
-        int e1 = left  + sixth;
-        int e5 = right - sixth;
+    private static void sort(double[] a, int left,int right,boolean leftmost) {
+        int length = right - left + 1;
+
+        // Use insertion sort on tiny arrays
+        if (length < INSERTION_SORT_THRESHOLD) {
+            if (!leftmost) {
+                /*
+                 * Every element in adjoining part plays the role
+                 * of sentinel, therefore this allows us to avoid
+                 * the j >= left check on each iteration.
+                 */
+                for (int j, i = left + 1; i <= right; i++) {
+                    double ai = a[i];
+                    for (j = i - 1; ai < a[j]; j--) {
+                        // assert j >= left;
+                        a[j + 1] = a[j];
+                    }
+                    a[j + 1] = ai;
+                }
+            } else {
+                /*
+                 * For case of leftmost part traditional (without a sentinel)
+                 * insertion sort, optimized for server JVM, is used.
+                 */
+                for (int i = left, j = i; i < right; j = ++i) {
+                    double ai = a[i + 1];
+                    while (ai < a[j]) {
+                        a[j + 1] = a[j];
+                        if (j-- == left) {
+                            break;
+                        }
+                    }
+                    a[j + 1] = ai;
+                }
+            }
+            return;
+        }
+
+        // Inexpensive approximation of length / 7
+        int seventh = (length >>> 3) + (length >>> 6) + 1;
+
+        /*
+         * Sort five evenly spaced elements around (and including) the
+         * center element in the range. These elements will be used for
+         * pivot selection as described below. The choice for spacing
+         * these elements was empirically determined to work well on
+         * a wide variety of inputs.
+         */
         int e3 = (left + right) >>> 1; // The midpoint
-        int e4 = e3 + sixth;
-        int e2 = e3 - sixth;
+        int e2 = e3 - seventh;
+        int e1 = e2 - seventh;
+        int e4 = e3 + seventh;
+        int e5 = e4 + seventh;
 
-        // Sort these elements using a 5-element sorting network
-        double ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+        // Sort these elements using insertion sort
+        if (a[e2] < a[e1]) { double t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
 
-        if (ae1 > ae2) { double t = ae1; ae1 = ae2; ae2 = t; }
-        if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; }
-        if (ae1 > ae3) { double t = ae1; ae1 = ae3; ae3 = t; }
-        if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; }
-        if (ae1 > ae4) { double t = ae1; ae1 = ae4; ae4 = t; }
-        if (ae3 > ae4) { double t = ae3; ae3 = ae4; ae4 = t; }
-        if (ae2 > ae5) { double t = ae2; ae2 = ae5; ae5 = t; }
-        if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; }
-        if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; }
-
-        a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+        if (a[e3] < a[e2]) { double t = a[e3]; a[e3] = a[e2]; a[e2] = t;
+            if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+        }
+        if (a[e4] < a[e3]) { double t = a[e4]; a[e4] = a[e3]; a[e3] = t;
+            if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+                if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+            }
+        }
+        if (a[e5] < a[e4]) { double t = a[e5]; a[e5] = a[e4]; a[e4] = t;
+            if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
+                if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
+                    if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
+                }
+            }
+        }
 
         /*
          * Use the second and fourth of the five sorted elements as pivots.
          * These values are inexpensive approximations of the first and
          * second terciles of the array. Note that pivot1 <= pivot2.
-         *
-         * The pivots are stored in local variables, and the first and
-         * the last of the elements to be sorted are moved to the locations
-         * formerly occupied by the pivots. When partitioning is complete,
-         * the pivots are swapped back into their final positions, and
-         * excluded from subsequent sorting.
          */
-        double pivot1 = ae2; a[e2] = a[left];
-        double pivot2 = ae4; a[e4] = a[right];
+        double pivot1 = a[e2];
+        double pivot2 = a[e4];
 
         // Pointers
-        int less  = left  + 1; // The index of first element of center part
-        int great = right - 1; // The index before first element of right part
+        int less  = left;  // The index of the first element of center part
+        int great = right; // The index before the first element of right part
 
-        boolean pivotsDiffer = (pivot1 != pivot2);
+        if (pivot1 != pivot2) {
+            /*
+             * The first and the last elements to be sorted are moved to the
+             * locations formerly occupied by the pivots. When partitioning
+             * is complete, the pivots are swapped back into their final
+             * positions, and excluded from subsequent sorting.
+             */
+            a[e2] = a[left];
+            a[e4] = a[right];
 
-        if (pivotsDiffer) {
+            /*
+             * Skip elements, which are less or greater than pivot values.
+             */
+            while (a[++less] < pivot1);
+            while (a[--great] > pivot2);
+
             /*
              * Partitioning:
              *
-             *   left part         center part                    right part
-             * +------------------------------------------------------------+
-             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
-             * +------------------------------------------------------------+
-             *              ^                          ^       ^
-             *              |                          |       |
-             *             less                        k     great
+             *   left part           center part                   right part
+             * +--------------------------------------------------------------+
+             * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
+             * +--------------------------------------------------------------+
+             *               ^                          ^       ^
+             *               |                          |       |
+             *              less                        k     great
              *
              * Invariants:
              *
@@ -2101,16 +2541,14 @@
              *    pivot1 <= all in [less, k)     <= pivot2
              *              all in (great, right) > pivot2
              *
-             * Pointer k is the first index of ?-part
+             * Pointer k is the first index of ?-part.
              */
             outer:
             for (int k = less; k <= great; k++) {
                 double ak = a[k];
                 if (ak < pivot1) { // Move a[k] to left part
-                    if (k != less) {
-                        a[k] = a[less];
-                        a[less] = ak;
-                    }
+                    a[k] = a[less];
+                    a[less] = ak;
                     less++;
                 } else if (ak > pivot2) { // Move a[k] to right part
                     while (a[great] > pivot2) {
@@ -2120,26 +2558,107 @@
                     }
                     if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = a[great];
-                        a[great--] = ak;
+                        a[less] = a[great];
+                        less++;
                     } else { // pivot1 <= a[great] <= pivot2
                         a[k] = a[great];
-                        a[great--] = ak;
+                    }
+                    a[great] = ak;
+                    great--;
+                }
+            }
+
+            // Swap pivots into their final positions
+            a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
+            a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+            // Sort left and right parts recursively, excluding known pivots
+            sort(a, left, less - 2, leftmost);
+            sort(a, great + 2, right, false);
+
+            /*
+             * If center part is too large (comprises > 5/7 of the array),
+             * swap internal pivot values to ends.
+             */
+            if (less < e1 && e5 < great) {
+                /*
+                 * Skip elements, which are equal to pivot values.
+                 */
+                while (a[less] == pivot1) {
+                    less++;
+                }
+                while (a[great] == pivot2) {
+                    great--;
+                }
+
+                /*
+                 * Partitioning:
+                 *
+                 *   left part         center part                  right part
+                 * +----------------------------------------------------------+
+                 * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
+                 * +----------------------------------------------------------+
+                 *              ^                        ^       ^
+                 *              |                        |       |
+                 *             less                      k     great
+                 *
+                 * Invariants:
+                 *
+                 *              all in (*,  less) == pivot1
+                 *     pivot1 < all in [less,  k)  < pivot2
+                 *              all in (great, *) == pivot2
+                 *
+                 * Pointer k is the first index of ?-part.
+                 */
+                outer:
+                for (int k = less; k <= great; k++) {
+                    double ak = a[k];
+                    if (ak == pivot1) { // Move a[k] to left part
+                        a[k] = a[less];
+                        a[less] = ak;
+                        less++;
+                    } else if (ak == pivot2) { // Move a[k] to right part
+                        while (a[great] == pivot2) {
+                            if (great-- == k) {
+                                break outer;
+                            }
+                        }
+                        if (a[great] == pivot1) {
+                            a[k] = a[less];
+                            /*
+                             * Even though a[great] equals to pivot1, the
+                             * assignment a[less] = pivot1 may be incorrect,
+                             * if a[great] and pivot1 are floating-point zeros
+                             * of different signs. Therefore in float and
+                             * double sorting methods we have to use more
+                             * accurate assignment a[less] = a[great].
+                             */
+                            a[less] = a[great];
+                            less++;
+                        } else { // pivot1 < a[great] < pivot2
+                            a[k] = a[great];
+                        }
+                        a[great] = ak;
+                        great--;
                     }
                 }
             }
+
+            // Sort center part recursively
+            sort(a, less, great, false);
+
         } else { // Pivots are equal
             /*
-             * Partition degenerates to the traditional 3-way,
-             * or "Dutch National Flag", partition:
+             * Partition degenerates to the traditional 3-way
+             * (or "Dutch National Flag") schema:
              *
-             *   left part   center part            right part
-             * +----------------------------------------------+
-             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
-             * +----------------------------------------------+
-             *              ^            ^       ^
-             *              |            |       |
-             *             less          k     great
+             *   left part    center part              right part
+             * +-------------------------------------------------+
+             * |  < pivot  |   == pivot   |     ?    |  > pivot  |
+             * +-------------------------------------------------+
+             *              ^              ^        ^
+             *              |              |        |
+             *             less            k      great
              *
              * Invariants:
              *
@@ -2147,20 +2666,19 @@
              *   all in [less, k)     == pivot
              *   all in (great, right) > pivot
              *
-             * Pointer k is the first index of ?-part
+             * Pointer k is the first index of ?-part.
              */
-            for (int k = less; k <= great; k++) {
-                double ak = a[k];
-                if (ak == pivot1) {
+            for (int k = left; k <= great; k++) {
+                if (a[k] == pivot1) {
                     continue;
                 }
+                double ak = a[k];
+
                 if (ak < pivot1) { // Move a[k] to left part
-                    if (k != less) {
-                        a[k] = a[less];
-                        a[less] = ak;
-                    }
+                    a[k] = a[less];
+                    a[less] = ak;
                     less++;
-                } else { // (a[k] > pivot1) - Move a[k] to right part
+                } else { // a[k] > pivot1 - Move a[k] to right part
                     /*
                      * We know that pivot1 == a[e3] == pivot2. Thus, we know
                      * that great will still be >= k when the following loop
@@ -2168,102 +2686,43 @@
                      * In other words, a[e3] acts as a sentinel for great.
                      */
                     while (a[great] > pivot1) {
+                        // assert great > k;
                         great--;
                     }
                     if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = a[great];
-                        a[great--] = ak;
+                        a[less] = a[great];
+                        less++;
                     } else { // a[great] == pivot1
-                        a[k] = pivot1;
-                        a[great--] = ak;
+                        /*
+                         * Even though a[great] equals to pivot1, the
+                         * assignment a[k] = pivot1 may be incorrect,
+                         * if a[great] and pivot1 are floating-point
+                         * zeros of different signs. Therefore in float
+                         * and double sorting methods we have to use
+                         * more accurate assignment a[k] = a[great].
+                         */
+                        a[k] = a[great];
                     }
+                    a[great] = ak;
+                    great--;
                 }
             }
+
+            // Sort left and right parts recursively
+            sort(a, left, less - 1, leftmost);
+            sort(a, great + 1, right, false);
         }
-
-        // Swap pivots into their final positions
-        a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
-        a[right] = a[great + 1]; a[great + 1] = pivot2;
-
-        // Sort left and right parts recursively, excluding known pivot values
-        doSort(a, left,   less - 2);
-        doSort(a, great + 2, right);
-
-        /*
-         * If pivot1 == pivot2, all elements from center
-         * part are equal and, therefore, already sorted
-         */
-        if (!pivotsDiffer) {
-            return;
-        }
-
-        /*
-         * If center part is too large (comprises > 2/3 of the array),
-         * swap internal pivot values to ends
-         */
-        if (less < e1 && great > e5) {
-            while (a[less] == pivot1) {
-                less++;
-            }
-            while (a[great] == pivot2) {
-                great--;
-            }
-
-            /*
-             * Partitioning:
-             *
-             *   left part       center part                   right part
-             * +----------------------------------------------------------+
-             * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
-             * +----------------------------------------------------------+
-             *              ^                        ^       ^
-             *              |                        |       |
-             *             less                      k     great
-             *
-             * Invariants:
-             *
-             *              all in (*, less)  == pivot1
-             *     pivot1 < all in [less, k)   < pivot2
-             *              all in (great, *) == pivot2
-             *
-             * Pointer k is the first index of ?-part
-             */
-            outer:
-            for (int k = less; k <= great; k++) {
-                double ak = a[k];
-                if (ak == pivot2) { // Move a[k] to right part
-                    while (a[great] == pivot2) {
-                        if (great-- == k) {
-                            break outer;
-                        }
-                    }
-                    if (a[great] == pivot1) {
-                        a[k] = a[less];
-                        a[less++] = pivot1;
-                    } else { // pivot1 < a[great] < pivot2
-                        a[k] = a[great];
-                    }
-                    a[great--] = pivot2;
-                } else if (ak == pivot1) { // Move a[k] to left part
-                    a[k] = a[less];
-                    a[less++] = pivot1;
-                }
-            }
-        }
-
-        // Sort center part recursively, excluding known pivot values
-        doSort(a, less, great);
     }
 
     /**
-     * Checks that {@code fromIndex} and {@code toIndex} are in
-     * the range and throws an appropriate exception, if they aren't.
+     * Checks that {@code fromIndex} and {@code toIndex} are in the range,
+     * otherwise throws an appropriate exception.
      */
     private static void rangeCheck(int length, int fromIndex, int toIndex) {
         if (fromIndex > toIndex) {
             throw new IllegalArgumentException(
-                "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
+                "fromIndex: " + fromIndex + " > toIndex: " + toIndex);
         }
         if (fromIndex < 0) {
             throw new ArrayIndexOutOfBoundsException(fromIndex);
--- a/test/java/util/Arrays/Sorting.java	Wed Jun 30 16:11:32 2010 -0700
+++ b/test/java/util/Arrays/Sorting.java	Thu Jul 01 16:28:08 2010 +0100
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2009, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
@@ -43,10 +43,11 @@
 
     // Array lengths used in a long run (default)
     private static final int[] LONG_RUN_LENGTHS = {
-        1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000};
+        1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000 };
 
     // Array lengths used in a short run
-    private static final int[] SHORT_RUN_LENGTHS = { 1, 2, 3, 21, 55, 1000, 10000 };
+    private static final int[] SHORT_RUN_LENGTHS = {
+        1, 2, 3, 21, 55, 1000, 10000 };
 
     // Random initial values used in a long run (default)
     private static final long[] LONG_RUN_RANDOMS = {666, 0xC0FFEE, 999};
@@ -65,99 +66,338 @@
         }
         long end = System.currentTimeMillis();
 
-        out.format("PASS in %d sec.\n", Math.round((end - start) / 1E3));
+        out.format("\nPASSED in %d sec.\n", Math.round((end - start) / 1E3));
     }
 
     private static void testAndCheck(int[] lengths, long[] randoms) {
+        testEmptyAndNullIntArray();
+        testEmptyAndNullLongArray();
+        testEmptyAndNullShortArray();
+        testEmptyAndNullCharArray();
+        testEmptyAndNullByteArray();
+        testEmptyAndNullFloatArray();
+        testEmptyAndNullDoubleArray();
+
         for (long random : randoms) {
             reset(random);
 
-            for (int len : lengths) {
-                testAndCheckWithCheckSum(len, random);
+            for (int length : lengths) {
+                testAndCheckWithCheckSum(length, random);
             }
             reset(random);
 
-            for (int len : lengths) {
-                testAndCheckWithScrambling(len, random);
+            for (int length : lengths) {
+                testAndCheckWithScrambling(length, random);
             }
             reset(random);
 
-            for (int len : lengths) {
-                testAndCheckFloat(len, random);
+            for (int length : lengths) {
+                testAndCheckFloat(length, random);
             }
             reset(random);
 
-            for (int len : lengths) {
-                testAndCheckDouble(len, random);
+            for (int length : lengths) {
+                testAndCheckDouble(length, random);
             }
             reset(random);
 
-            for (int len : lengths) {
-                testAndCheckRange(len, random);
+            for (int length : lengths) {
+                testAndCheckRange(length, random);
             }
             reset(random);
 
-            for (int len : lengths) {
-                testAndCheckSubArray(len, random);
+            for (int length : lengths) {
+                testAndCheckSubArray(length, random);
+            }
+            reset(random);
+
+            for (int length : lengths) {
+                testStable(length, random);
             }
         }
     }
 
-    private static void testAndCheckSubArray(int len, long random) {
-        int[] golden = new int[len];
+    private static void testEmptyAndNullIntArray() {
+        ourDescription = "Check empty and null array";
+        Arrays.sort(new int[] {});
+        Arrays.sort(new int[] {}, 0, 0);
 
-        for (int m = 1; m < len / 2; m *= 2) {
+        try {
+            Arrays.sort((int[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                Arrays.sort((int[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("Arrays.sort(int[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("Arrays.sort(int[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullLongArray() {
+        ourDescription = "Check empty and null array";
+        Arrays.sort(new long[] {});
+        Arrays.sort(new long[] {}, 0, 0);
+
+        try {
+            Arrays.sort((long[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                Arrays.sort((long[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("Arrays.sort(long[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("Arrays.sort(long[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullShortArray() {
+        ourDescription = "Check empty and null array";
+        Arrays.sort(new short[] {});
+        Arrays.sort(new short[] {}, 0, 0);
+
+        try {
+            Arrays.sort((short[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                Arrays.sort((short[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("Arrays.sort(short[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("Arrays.sort(short[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullCharArray() {
+        ourDescription = "Check empty and null array";
+        Arrays.sort(new char[] {});
+        Arrays.sort(new char[] {}, 0, 0);
+
+        try {
+            Arrays.sort((char[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                Arrays.sort((char[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("Arrays.sort(char[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("Arrays.sort(char[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullByteArray() {
+        ourDescription = "Check empty and null array";
+        Arrays.sort(new byte[] {});
+        Arrays.sort(new byte[] {}, 0, 0);
+
+        try {
+            Arrays.sort((byte[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                Arrays.sort((byte[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("Arrays.sort(byte[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("Arrays.sort(byte[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullFloatArray() {
+        ourDescription = "Check empty and null array";
+        Arrays.sort(new float[] {});
+        Arrays.sort(new float[] {}, 0, 0);
+
+        try {
+            Arrays.sort((float[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                Arrays.sort((float[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("Arrays.sort(float[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("Arrays.sort(float[]) shouldn't catch null array");
+    }
+
+    private static void testEmptyAndNullDoubleArray() {
+        ourDescription = "Check empty and null array";
+        Arrays.sort(new double[] {});
+        Arrays.sort(new double[] {}, 0, 0);
+
+        try {
+            Arrays.sort((double[]) null);
+        } catch (NullPointerException expected) {
+            try {
+                Arrays.sort((double[]) null, 0, 0);
+            } catch (NullPointerException expected2) {
+                return;
+            }
+            failed("Arrays.sort(double[],fromIndex,toIndex) shouldn't " +
+                "catch null array");
+        }
+        failed("Arrays.sort(double[]) shouldn't catch null array");
+    }
+
+    private static void testAndCheckSubArray(int length, long random) {
+        ourDescription = "Check sorting of subarray";
+        int[] golden = new int[length];
+        boolean newLine = false;
+
+        for (int m = 1; m < length / 2; m *= 2) {
+            newLine = true;
             int fromIndex = m;
-            int toIndex = len - m;
+            int toIndex = length - m;
 
             prepareSubArray(golden, fromIndex, toIndex, m);
             int[] test = golden.clone();
 
             for (TypeConverter converter : TypeConverter.values()) {
-                out.println("Test #6: " + converter +
-                   " len = " + len + ", m = " + m);
+                out.println("Test 'subarray': " + converter +
+                   " length = " + length + ", m = " + m);
                 Object convertedGolden = converter.convert(golden);
                 Object convertedTest = converter.convert(test);
+                // outArray(test);
+                sortSubArray(convertedTest, fromIndex, toIndex);
+                // outArray(test);
+                checkSubArray(convertedTest, fromIndex, toIndex, m);
+            }
+        }
+        if (newLine) {
+            out.println();
+        }
+    }
 
-                // outArr(test);
-                sortSubArray(convertedTest, fromIndex, toIndex);
-                // outArr(test);
-                checkSubArray(convertedTest, fromIndex, toIndex, m);
+    private static void testAndCheckRange(int length, long random) {
+        ourDescription = "Check range check";
+        int[] golden = new int[length];
+
+        for (int m = 1; m < 2 * length; m *= 2) {
+            for (int i = 1; i <= length; i++) {
+                golden[i - 1] = i % m + m % i;
+            }
+            for (TypeConverter converter : TypeConverter.values()) {
+                out.println("Test 'range': " + converter +
+                   ", length = " + length + ", m = " + m);
+                Object convertedGolden = converter.convert(golden);
+                checkRange(convertedGolden, m);
             }
         }
         out.println();
     }
 
-    private static void testAndCheckRange(int len, long random) {
-        int[] golden = new int[len];
+    private static void testStable(int length, long random) {
+        ourDescription = "Check if sorting is stable";
+        Pair[] a = build(length);
 
-        for (int m = 1; m < 2 * len; m *= 2) {
-            for (int i = 1; i <= len; i++) {
-                golden[i - 1] = i % m + m % i;
-            }
-            for (TypeConverter converter : TypeConverter.values()) {
-                out.println("Test #5: " + converter +
-                   ", len = " + len + ", m = " + m);
-                Object convertedGolden = converter.convert(golden);
-                sortRange(convertedGolden, m);
-                sortEmpty(convertedGolden);
+        out.println("Test 'stable': " + "random = " +  random +
+            ", length = " + length);
+        Arrays.sort(a);
+        checkSorted(a);
+        checkStable(a);
+    }
+
+    private static void checkSorted(Pair[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i].getKey() > a[i + 1].getKey()) {
+                failed(i, "" + a[i].getKey(), "" + a[i + 1].getKey());
             }
         }
-        out.println();
     }
 
-    private static void testAndCheckWithCheckSum(int len, long random) {
-        int[] golden = new int[len];
+    private static void checkStable(Pair[] a) {
+        for (int i = 0; i < a.length / 4; ) {
+            int key1 = a[i].getKey();
+            int value1 = a[i++].getValue();
+            int key2 = a[i].getKey();
+            int value2 = a[i++].getValue();
+            int key3 = a[i].getKey();
+            int value3 = a[i++].getValue();
+            int key4 = a[i].getKey();
+            int value4 = a[i++].getValue();
 
-        for (int m = 1; m < 2 * len; m *= 2) {
+            if (!(key1 == key2 && key2 == key3 && key3 == key4)) {
+                failed("On position " + i + " must keys are different " +
+                    key1 + ", " + key2 + ", " + key3 + ", " + key4);
+            }
+            if (!(value1 < value2 && value2 < value3 && value3 < value4)) {
+                failed("Sorting is not stable at position " + i +
+                    ". Second values have been changed: " +  value1 + ", " +
+                    value2 + ", " + value3 + ", " + value4);
+            }
+        }
+    }
+
+    private static Pair[] build(int length) {
+        Pair[] a = new Pair[length * 4];
+
+        for (int i = 0; i < a.length; ) {
+            int key = ourRandom.nextInt();
+            a[i++] = new Pair(key, 1);
+            a[i++] = new Pair(key, 2);
+            a[i++] = new Pair(key, 3);
+            a[i++] = new Pair(key, 4);
+        }
+        return a;
+    }
+
+    private static final class Pair implements Comparable<Pair> {
+        Pair(int key, int value) {
+            myKey = key;
+            myValue = value;
+        }
+
+        int getKey() {
+            return myKey;
+        }
+
+        int getValue() {
+            return myValue;
+        }
+
+        public int compareTo(Pair pair) {
+            if (myKey < pair.myKey) {
+                return -1;
+            }
+            if (myKey > pair.myKey) {
+                return 1;
+            }
+            return 0;
+        }
+
+        @Override
+        public String toString() {
+            return "(" + myKey + ", " + myValue + ")";
+        }
+
+        private int myKey;
+        private int myValue;
+    }
+
+    private static void testAndCheckWithCheckSum(int length, long random) {
+        ourDescription = "Check sorting with check sum";
+        int[] golden = new int[length];
+
+        for (int m = 1; m < 2 * length; m *= 2) {
             for (UnsortedBuilder builder : UnsortedBuilder.values()) {
                 builder.build(golden, m);
                 int[] test = golden.clone();
 
                 for (TypeConverter converter : TypeConverter.values()) {
-                    out.println("Test #1: " + converter + " " + builder +
-                       "random = " +  random + ", len = " + len +
-                       ", m = " + m);
+                    out.println("Test 'check sum': " + converter + " " +
+                        builder + "random = " +  random + ", length = " +
+                        length + ", m = " + m);
                     Object convertedGolden = converter.convert(golden);
                     Object convertedTest = converter.convert(test);
                     sort(convertedTest);
@@ -168,11 +408,12 @@
         out.println();
     }
 
-    private static void testAndCheckWithScrambling(int len, long random) {
-        int[] golden = new int[len];
+    private static void testAndCheckWithScrambling(int length, long random) {
+        ourDescription = "Check sorting with scrambling";
+        int[] golden = new int[length];
 
         for (int m = 1; m <= 7; m++) {
-            if (m > len) {
+            if (m > length) {
                 break;
             }
             for (SortedBuilder builder : SortedBuilder.values()) {
@@ -181,9 +422,9 @@
                 scramble(test);
 
                 for (TypeConverter converter : TypeConverter.values()) {
-                    out.println("Test #2: " + converter + " " + builder +
-                       "random = " +  random + ", len = " + len +
-                       ", m = " + m);
+                    out.println("Test 'scrambling': " + converter + " " +
+                       builder + "random = " +  random + ", length = " +
+                       length + ", m = " + m);
                     Object convertedGolden = converter.convert(golden);
                     Object convertedTest = converter.convert(test);
                     sort(convertedTest);
@@ -194,8 +435,9 @@
         out.println();
     }
 
-    private static void testAndCheckFloat(int len, long random) {
-        float[] golden = new float[len];
+    private static void testAndCheckFloat(int length, long random) {
+        ourDescription = "Check float sorting";
+        float[] golden = new float[length];
         final int MAX = 10;
         boolean newLine = false;
 
@@ -204,22 +446,23 @@
                 for (int z = 0; z <= MAX; z++) {
                     for (int n = 0; n <= MAX; n++) {
                         for (int p = 0; p <= MAX; p++) {
-                            if (a + g + z + n + p > len) {
+                            if (a + g + z + n + p > length) {
                                 continue;
                             }
-                            if (a + g + z + n + p < len) {
+                            if (a + g + z + n + p < length) {
                                 continue;
                             }
                             for (FloatBuilder builder : FloatBuilder.values()) {
-                                out.println("Test #3: random = " + random +
-                                   ", len = " + len + ", a = " + a + ", g = " + g +
-                                   ", z = " + z + ", n = " + n + ", p = " + p);
+                                out.println("Test 'float': random = " + random +
+                                   ", length = " + length + ", a = " + a +
+                                   ", g = " + g + ", z = " + z + ", n = " + n +
+                                   ", p = " + p);
                                 builder.build(golden, a, g, z, n, p);
                                 float[] test = golden.clone();
                                 scramble(test);
-                                // outArr(test);
+                                // outArray(test);
                                 sort(test);
-                                // outArr(test);
+                                // outArray(test);
                                 compare(test, golden, a, n, g);
                             }
                             newLine = true;
@@ -233,8 +476,9 @@
         }
     }
 
-    private static void testAndCheckDouble(int len, long random) {
-        double[] golden = new double[len];
+    private static void testAndCheckDouble(int length, long random) {
+        ourDescription = "Check double sorting";
+        double[] golden = new double[length];
         final int MAX = 10;
         boolean newLine = false;
 
@@ -243,22 +487,22 @@
                 for (int z = 0; z <= MAX; z++) {
                     for (int n = 0; n <= MAX; n++) {
                         for (int p = 0; p <= MAX; p++) {
-                            if (a + g + z + n + p > len) {
+                            if (a + g + z + n + p > length) {
                                 continue;
                             }
-                            if (a + g + z + n + p < len) {
+                            if (a + g + z + n + p < length) {
                                 continue;
                             }
                             for (DoubleBuilder builder : DoubleBuilder.values()) {
-                                out.println("Test #4: random = " + random +
-                                   ", len = " + len + ", a = " + a + ", g = " + g +
-                                   ", z = " + z + ", n = " + n + ", p = " + p);
+                                out.println("Test 'double': random = " + random +
+                                   ", length = " + length + ", a = " + a + ", g = " +
+                                   g + ", z = " + z + ", n = " + n + ", p = " + p);
                                 builder.build(golden, a, g, z, n, p);
                                 double[] test = golden.clone();
                                 scramble(test);
-                                // outArr(test);
+                                // outArray(test);
                                 sort(test);
-                                // outArr(test);
+                                // outArray(test);
                                 compare(test, golden, a, n, g);
                             }
                             newLine = true;
@@ -276,37 +520,29 @@
         for (int i = 0; i < fromIndex; i++) {
             a[i] = 0xBABA;
         }
-
         for (int i = fromIndex; i < toIndex; i++) {
             a[i] = -i + m;
         }
-
         for (int i = toIndex; i < a.length; i++) {
             a[i] = 0xDEDA;
         }
     }
 
     private static void scramble(int[] a) {
-        int length = a.length;
-
-        for (int i = 0; i < length * 7; i++) {
-            swap(a, ourRandom.nextInt(length), ourRandom.nextInt(length));
+        for (int i = 0; i < a.length * 7; i++) {
+            swap(a, ourRandom.nextInt(a.length), ourRandom.nextInt(a.length));
         }
     }
 
     private static void scramble(float[] a) {
-        int length = a.length;
-
-        for (int i = 0; i < length * 7; i++) {
-            swap(a, ourRandom.nextInt(length), ourRandom.nextInt(length));
+        for (int i = 0; i < a.length * 7; i++) {
+            swap(a, ourRandom.nextInt(a.length), ourRandom.nextInt(a.length));
         }
     }
 
     private static void scramble(double[] a) {
-        int length = a.length;
-
-        for (int i = 0; i < length * 7; i++) {
-            swap(a, ourRandom.nextInt(length), ourRandom.nextInt(length));
+        for (int i = 0; i < a.length * 7; i++) {
+            swap(a, ourRandom.nextInt(a.length), ourRandom.nextInt(a.length));
         }
     }
 
@@ -393,6 +629,16 @@
                 }
                 return b;
             }
+        },
+        INTEGER {
+            Object convert(int[] a) {
+                Integer[] b = new Integer[a.length];
+
+                for (int i = 0; i < a.length; i++) {
+                    b[i] = new Integer(a[i]);
+                }
+                return b;
+            }
         };
 
         abstract Object convert(int[] a);
@@ -691,6 +937,8 @@
             compare((float[]) test, (float[]) golden);
         } else if (test instanceof double[]) {
             compare((double[]) test, (double[]) golden);
+        } else if (test instanceof Integer[]) {
+            compare((Integer[]) test, (Integer[]) golden);
         } else {
             failed("Unknow type of array: " + test + " of class " +
                 test.getClass().getName());
@@ -703,13 +951,13 @@
     }
 
     private static void failed(String message) {
-        err.format("\n*** FAILED: %s\n\n", message);
+        err.format("\n*** TEST FAILED - %s\n\n%s\n\n", ourDescription, message);
         throw new RuntimeException("Test failed - see log file for details");
     }
 
     private static void failed(int index, String value1, String value2) {
-        failed("Array is not sorted at " + index + "-th position: " + value1 +
-               " and " + value2);
+        failed("Array is not sorted at " + index + "-th position: " +
+            value1 + " and " + value2);
     }
 
     private static void checkSorted(Object object) {
@@ -727,12 +975,22 @@
             checkSorted((float[]) object);
         } else if (object instanceof double[]) {
             checkSorted((double[]) object);
+        } else if (object instanceof Integer[]) {
+            checkSorted((Integer[]) object);
         } else {
             failed("Unknow type of array: " + object + " of class " +
                 object.getClass().getName());
         }
     }
 
+    private static void compare(Integer[] a, Integer[] b) {
+        for (int i = 0; i < a.length; i++) {
+            if (a[i].intValue() != b[i].intValue()) {
+                failed(i, "" + a[i], "" + b[i]);
+            }
+        }
+    }
+
     private static void compare(int[] a, int[] b) {
         for (int i = 0; i < a.length; i++) {
             if (a[i] != b[i]) {
@@ -789,6 +1047,14 @@
         }
     }
 
+    private static void checkSorted(Integer[] a) {
+        for (int i = 0; i < a.length - 1; i++) {
+            if (a[i].intValue() > a[i + 1].intValue()) {
+                failed(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+    }
+
     private static void checkSorted(int[] a) {
         for (int i = 0; i < a.length - 1; i++) {
             if (a[i] > a[i + 1]) {
@@ -847,7 +1113,7 @@
 
     private static void checkCheckSum(Object test, Object golden) {
         if (checkSum(test) != checkSum(golden)) {
-            failed("Original and sorted arrays seems not identical");
+            failed("It seems that original and sorted arrays are not identical");
         }
     }
 
@@ -866,6 +1132,8 @@
             return checkSum((float[]) object);
         } else if (object instanceof double[]) {
             return checkSum((double[]) object);
+        } else if (object instanceof Integer[]) {
+            return checkSum((Integer[]) object);
         } else {
             failed("Unknow type of array: " + object + " of class " +
                 object.getClass().getName());
@@ -873,6 +1141,15 @@
         }
     }
 
+    private static int checkSum(Integer[] a) {
+        int checkXorSum = 0;
+
+        for (Integer e : a) {
+            checkXorSum ^= e.intValue();
+        }
+        return checkXorSum;
+    }
+
     private static int checkSum(int[] a) {
         int checkXorSum = 0;
 
@@ -951,6 +1228,8 @@
             Arrays.sort((float[]) object);
         } else if (object instanceof double[]) {
             Arrays.sort((double[]) object);
+        } else if (object instanceof Integer[]) {
+            Arrays.sort((Integer[]) object);
         } else {
             failed("Unknow type of array: " + object + " of class " +
                 object.getClass().getName());
@@ -972,6 +1251,8 @@
             Arrays.sort((float[]) object, fromIndex, toIndex);
         } else if (object instanceof double[]) {
             Arrays.sort((double[]) object, fromIndex, toIndex);
+        } else if (object instanceof Integer[]) {
+            Arrays.sort((Integer[]) object, fromIndex, toIndex);
         } else {
             failed("Unknow type of array: " + object + " of class " +
                 object.getClass().getName());
@@ -993,12 +1274,36 @@
             checkSubArray((float[]) object, fromIndex, toIndex, m);
         } else if (object instanceof double[]) {
             checkSubArray((double[]) object, fromIndex, toIndex, m);
+        } else if (object instanceof Integer[]) {
+            checkSubArray((Integer[]) object, fromIndex, toIndex, m);
         } else {
             failed("Unknow type of array: " + object + " of class " +
                 object.getClass().getName());
         }
     }
 
+    private static void checkSubArray(Integer[] a, int fromIndex, int toIndex, int m) {
+        for (int i = 0; i < fromIndex; i++) {
+            if (a[i].intValue() != 0xBABA) {
+                failed("Range sort changes left element on position " + i +
+                    ": " + a[i] + ", must be " + 0xBABA);
+            }
+        }
+
+        for (int i = fromIndex; i < toIndex - 1; i++) {
+            if (a[i].intValue() > a[i + 1].intValue()) {
+                failed(i, "" + a[i], "" + a[i + 1]);
+            }
+        }
+
+        for (int i = toIndex; i < a.length; i++) {
+            if (a[i].intValue() != 0xDEDA) {
+                failed("Range sort changes right element on position " + i +
+                    ": " + a[i] + ", must be " + 0xDEDA);
+            }
+        }
+    }
+
     private static void checkSubArray(int[] a, int fromIndex, int toIndex, int m) {
         for (int i = 0; i < fromIndex; i++) {
             if (a[i] != 0xBABA) {
@@ -1153,49 +1458,30 @@
         }
     }
 
-    private static void sortRange(Object object, int m) {
+    private static void checkRange(Object object, int m) {
         if (object instanceof int[]) {
-            sortRange((int[]) object, m);
+            checkRange((int[]) object, m);
         } else if (object instanceof long[]) {
-            sortRange((long[]) object, m);
+            checkRange((long[]) object, m);
         } else if (object instanceof short[]) {
-            sortRange((short[]) object, m);
+            checkRange((short[]) object, m);
         } else if (object instanceof byte[]) {
-            sortRange((byte[]) object, m);
+            checkRange((byte[]) object, m);
         } else if (object instanceof char[]) {
-            sortRange((char[]) object, m);
+            checkRange((char[]) object, m);
         } else if (object instanceof float[]) {
-            sortRange((float[]) object, m);
+            checkRange((float[]) object, m);
         } else if (object instanceof double[]) {
-            sortRange((double[]) object, m);
+            checkRange((double[]) object, m);
+        } else if (object instanceof Integer[]) {
+            checkRange((Integer[]) object, m);
         } else {
             failed("Unknow type of array: " + object + " of class " +
                 object.getClass().getName());
         }
     }
 
-    private static void sortEmpty(Object object) {
-        if (object instanceof int[]) {
-            Arrays.sort(new int [] {});
-        } else if (object instanceof long[]) {
-            Arrays.sort(new long [] {});
-        } else if (object instanceof short[]) {
-            Arrays.sort(new short [] {});
-        } else if (object instanceof byte[]) {
-            Arrays.sort(new byte [] {});
-        } else if (object instanceof char[]) {
-            Arrays.sort(new char [] {});
-        } else if (object instanceof float[]) {
-            Arrays.sort(new float [] {});
-        } else if (object instanceof double[]) {
-            Arrays.sort(new double [] {});
-        } else {
-            failed("Unknow type of array: " + object + " of class " +
-                object.getClass().getName());
-        }
-    }
-
-    private static void sortRange(int[] a, int m) {
+    private static void checkRange(Integer[] a, int m) {
         try {
             Arrays.sort(a, m + 1, m);
 
@@ -1224,7 +1510,7 @@
         }
     }
 
-    private static void sortRange(long[] a, int m) {
+    private static void checkRange(int[] a, int m) {
         try {
             Arrays.sort(a, m + 1, m);
 
@@ -1253,7 +1539,7 @@
         }
     }
 
-    private static void sortRange(byte[] a, int m) {
+    private static void checkRange(long[] a, int m) {
         try {
             Arrays.sort(a, m + 1, m);
 
@@ -1282,7 +1568,7 @@
         }
     }
 
-    private static void sortRange(short[] a, int m) {
+    private static void checkRange(byte[] a, int m) {
         try {
             Arrays.sort(a, m + 1, m);
 
@@ -1311,7 +1597,7 @@
         }
     }
 
-    private static void sortRange(char[] a, int m) {
+    private static void checkRange(short[] a, int m) {
         try {
             Arrays.sort(a, m + 1, m);
 
@@ -1340,7 +1626,7 @@
         }
     }
 
-    private static void sortRange(float[] a, int m) {
+    private static void checkRange(char[] a, int m) {
         try {
             Arrays.sort(a, m + 1, m);
 
@@ -1369,7 +1655,36 @@
         }
     }
 
-    private static void sortRange(double[] a, int m) {
+    private static void checkRange(float[] a, int m) {
+        try {
+            Arrays.sort(a, m + 1, m);
+
+            failed("Sort does not throw IllegalArgumentException " +
+                " as expected: fromIndex = " + (m + 1) +
+                " toIndex = " + m);
+        }
+        catch (IllegalArgumentException iae) {
+            try {
+                Arrays.sort(a, -m, a.length);
+
+                failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                    " as expected: fromIndex = " + (-m));
+            }
+            catch (ArrayIndexOutOfBoundsException aoe) {
+                try {
+                    Arrays.sort(a, 0, a.length + m);
+
+                    failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+                        " as expected: toIndex = " + (a.length + m));
+                }
+                catch (ArrayIndexOutOfBoundsException aie) {
+                    return;
+                }
+            }
+        }
+    }
+
+    private static void checkRange(double[] a, int m) {
         try {
             Arrays.sort(a, m + 1, m);
 
@@ -1410,31 +1725,36 @@
         ourSecond = 0;
     }
 
-    private static void outArr(int[] a) {
+    private static void outArray(Object[] a) {
         for (int i = 0; i < a.length; i++) {
             out.print(a[i] + " ");
         }
         out.println();
-        out.println();
     }
 
-    private static void outArr(float[] a) {
+    private static void outArray(int[] a) {
         for (int i = 0; i < a.length; i++) {
             out.print(a[i] + " ");
         }
         out.println();
-        out.println();
     }
 
-    private static void outArr(double[] a) {
+    private static void outArray(float[] a) {
         for (int i = 0; i < a.length; i++) {
             out.print(a[i] + " ");
         }
         out.println();
+    }
+
+    private static void outArray(double[] a) {
+        for (int i = 0; i < a.length; i++) {
+            out.print(a[i] + " ");
+        }
         out.println();
     }
 
     private static int ourFirst;
     private static int ourSecond;
     private static Random ourRandom;
+    private static String ourDescription;
 }