changeset 1961:146c8921267f

6905046: More Dual-pivot quicksort improvements Summary: More improvements from the DPQ team Reviewed-by: alanb
author jjb
date Tue, 08 Dec 2009 12:40:30 +0000
parents 0dcdb13ab6d0
children d7c07e9258a9 a0f6963b1618
files src/share/classes/java/util/DualPivotQuicksort.java
diffstat 1 files changed, 627 insertions(+), 403 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/DualPivotQuicksort.java	Mon Dec 07 16:44:40 2009 -0800
+++ b/src/share/classes/java/util/DualPivotQuicksort.java	Tue Dec 08 12:40:30 2009 +0000
@@ -36,12 +36,12 @@
  * @author Jon Bentley
  * @author Josh Bloch
  *
- * @version 2009.11.16 m765.827.v12a
+ * @version 2009.11.29 m765.827.12i
  */
 final class DualPivotQuicksort {
 
     /**
-     * Suppresses default constructor.
+     * Prevents instantiation.
      */
     private DualPivotQuicksort() {}
 
@@ -84,7 +84,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.
+     * the range to be sorted is empty (and the call is a no-op).
      *
      * @param a the array to be sorted
      * @param fromIndex the index of the first element, inclusive, to be sorted
@@ -101,8 +101,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}.
+     * {@code right} index is inclusive, and it does no range checking
+     * on {@code left} or {@code right}.
      *
      * @param a the array to be sorted
      * @param left the index of the first element, inclusive, to be sorted
@@ -111,13 +111,13 @@
     private static void doSort(int[] a, int left, int right) {
         // Use insertion sort on tiny arrays
         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
-            for (int k = left + 1; k <= right; k++) {
-                int ak = a[k];
+            for (int i = left + 1; i <= right; i++) {
+                int ai = a[i];
                 int j;
-                for (j = k - 1; j >= left && ak < a[j]; j--) {
+                for (j = i - 1; j >= left && ai < a[j]; j--) {
                     a[j + 1] = a[j];
                 }
-                a[j + 1] = ak;
+                a[j + 1] = ai;
             }
         } else { // Use Dual-Pivot Quicksort on large arrays
             dualPivotQuicksort(a, left, right);
@@ -162,7 +162,7 @@
          * second terciles of the array. Note that pivot1 <= pivot2.
          *
          * The pivots are stored in local variables, and the first and
-         * the last of the sorted elements are moved to the locations
+         * 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.
@@ -170,27 +170,26 @@
         int pivot1 = ae2; a[e2] = a[left];
         int pivot2 = ae4; a[e4] = a[right];
 
-        /*
-         * Partitioning
-         *
-         *   left part         center part                  right part
-         * ------------------------------------------------------------
-         * [ < pivot1  |  pivot1 <= && <= pivot2  |   ?   |  > pivot2 ]
-         * ------------------------------------------------------------
-         *              ^                          ^     ^
-         *              |                          |     |
-         *             less                        k   great
-         */
-
         // 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
 
-        boolean pivotsDiffer = pivot1 != pivot2;
+        boolean pivotsDiffer = (pivot1 != pivot2);
 
         if (pivotsDiffer) {
             /*
+             * Partitioning:
+             *
+             *   left part         center part                    right part
+             * +------------------------------------------------------------+
+             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
+             * +------------------------------------------------------------+
+             *              ^                          ^       ^
+             *              |                          |       |
+             *             less                        k     great
+             *
              * Invariants:
+             *
              *              all in (left, less)   < pivot1
              *    pivot1 <= all in [less, k)     <= pivot2
              *              all in (great, right) > pivot2
@@ -200,37 +199,37 @@
             outer:
             for (int k = less; k <= great; k++) {
                 int ak = a[k];
-                if (ak < pivot1) {
-                    if (k > less) {
+                if (ak < pivot1) { // Move a[k] to left part
+                    if (k != less) {
                         a[k] = a[less];
                         a[less] = ak;
                     }
                     less++;
-                } else if (ak > pivot2) {
+                } else if (ak > pivot2) { // Move a[k] to right part
                     while (a[great] > pivot2) {
-                        if (k == great--) {
+                        if (great-- == k) {
                             break outer;
                         }
                     }
-                    a[k] = a[great];
-                    a[great--] = ak;
-
-                    if ((ak = a[k]) < pivot1) {
+                    if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = ak;
+                        a[less++] = a[great];
+                        a[great--] = ak;
+                    } else { // pivot1 <= a[great] <= pivot2
+                        a[k] = a[great];
+                        a[great--] = ak;
                     }
                 }
             }
         } 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", partition:
              *
              *   left part   center part            right part
-             * -------------------------------------------------
-             * [  < pivot  |  == pivot  |    ?    |  > pivot   ]
-             * -------------------------------------------------
-             *
+             * +----------------------------------------------+
+             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
+             * +----------------------------------------------+
              *              ^            ^       ^
              *              |            |       |
              *             less          k     great
@@ -243,30 +242,34 @@
              *
              * Pointer k is the first index of ?-part
              */
-            outer:
             for (int k = less; k <= great; k++) {
                 int ak = a[k];
                 if (ak == pivot1) {
                     continue;
                 }
-                if (ak < pivot1) {
-                    if (k > less) {
+                if (ak < pivot1) { // Move a[k] to left part
+                    if (k != less) {
                         a[k] = a[less];
                         a[less] = ak;
                     }
                     less++;
-                } else { // a[k] > pivot
+                } 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
+                     * terminates, even though we don't test for it explicitly.
+                     * In other words, a[e3] acts as a sentinel for great.
+                     */
                     while (a[great] > pivot1) {
-                        if (k == great--) {
-                            break outer;
-                        }
+                        great--;
                     }
-                    a[k] = a[great];
-                    a[great--] = ak;
-
-                    if ((ak = a[k]) <  pivot1) {
+                    if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = ak;
+                        a[less++] = a[great];
+                        a[great--] = ak;
+                    } else { // a[great] == pivot1
+                        a[k] = pivot1;
+                        a[great--] = ak;
                     }
                 }
             }
@@ -289,26 +292,55 @@
         }
 
         /*
-         * If center part is too large (comprises > 5/6 of
-         * the array), swap internal pivot values to ends
+         * If center part is too large (comprises > 2/3 of the array),
+         * swap internal pivot values to ends
          */
-        if (less < e1 && e5 < great) {
+        if (less < e1 && great > e5) {
             while (a[less] == pivot1) {
                 less++;
             }
             while (a[great] == pivot2) {
                 great--;
             }
-            for (int k = less + 1; k <= 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) {
-                    a[k++] = a[less];
+                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;
-                } else if (ak == pivot2) {
-                    a[k] = a[great];
-                    a[great--] = pivot2;
-                } else {
-                    k++;
                 }
             }
         }
@@ -330,7 +362,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.
+     * the range to be sorted is empty (and the call is a no-op).
      *
      * @param a the array to be sorted
      * @param fromIndex the index of the first element, inclusive, to be sorted
@@ -357,13 +389,13 @@
     private static void doSort(long[] a, int left, int right) {
         // Use insertion sort on tiny arrays
         if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
-            for (int k = left + 1; k <= right; k++) {
-                long ak = a[k];
+            for (int i = left + 1; i <= right; i++) {
+                long ai = a[i];
                 int j;
-                for (j = k - 1; j >= left && ak < a[j]; j--) {
+                for (j = i - 1; j >= left && ai < a[j]; j--) {
                     a[j + 1] = a[j];
                 }
-                a[j + 1] = ak;
+                a[j + 1] = ai;
             }
         } else { // Use Dual-Pivot Quicksort on large arrays
             dualPivotQuicksort(a, left, right);
@@ -408,7 +440,7 @@
          * second terciles of the array. Note that pivot1 <= pivot2.
          *
          * The pivots are stored in local variables, and the first and
-         * the last of the sorted elements are moved to the locations
+         * 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.
@@ -416,27 +448,26 @@
         long pivot1 = ae2; a[e2] = a[left];
         long pivot2 = ae4; a[e4] = a[right];
 
-        /*
-         * Partitioning
-         *
-         *   left part         center part                  right part
-         * ------------------------------------------------------------
-         * [ < pivot1  |  pivot1 <= && <= pivot2  |   ?   |  > pivot2 ]
-         * ------------------------------------------------------------
-         *              ^                          ^     ^
-         *              |                          |     |
-         *             less                        k   great
-         */
-
         // 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
 
-        boolean pivotsDiffer = pivot1 != pivot2;
+        boolean pivotsDiffer = (pivot1 != pivot2);
 
         if (pivotsDiffer) {
             /*
+             * Partitioning:
+             *
+             *   left part         center part                    right part
+             * +------------------------------------------------------------+
+             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
+             * +------------------------------------------------------------+
+             *              ^                          ^       ^
+             *              |                          |       |
+             *             less                        k     great
+             *
              * Invariants:
+             *
              *              all in (left, less)   < pivot1
              *    pivot1 <= all in [less, k)     <= pivot2
              *              all in (great, right) > pivot2
@@ -446,37 +477,37 @@
             outer:
             for (int k = less; k <= great; k++) {
                 long ak = a[k];
-                if (ak < pivot1) {
-                    if (k > less) {
+                if (ak < pivot1) { // Move a[k] to left part
+                    if (k != less) {
                         a[k] = a[less];
                         a[less] = ak;
                     }
                     less++;
-                } else if (ak > pivot2) {
+                } else if (ak > pivot2) { // Move a[k] to right part
                     while (a[great] > pivot2) {
-                        if (k == great--) {
+                        if (great-- == k) {
                             break outer;
                         }
                     }
-                    a[k] = a[great];
-                    a[great--] = ak;
-
-                    if ((ak = a[k]) <  pivot1) {
+                    if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = ak;
+                        a[less++] = a[great];
+                        a[great--] = ak;
+                    } else { // pivot1 <= a[great] <= pivot2
+                        a[k] = a[great];
+                        a[great--] = ak;
                     }
                 }
             }
         } 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", partition:
              *
              *   left part   center part            right part
-             * -------------------------------------------------
-             * [  < pivot  |  == pivot  |    ?    |  > pivot   ]
-             * -------------------------------------------------
-             *
+             * +----------------------------------------------+
+             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
+             * +----------------------------------------------+
              *              ^            ^       ^
              *              |            |       |
              *             less          k     great
@@ -489,30 +520,34 @@
              *
              * Pointer k is the first index of ?-part
              */
-            outer:
             for (int k = less; k <= great; k++) {
                 long ak = a[k];
                 if (ak == pivot1) {
                     continue;
                 }
-                if (ak < pivot1) {
-                    if (k > less) {
+                if (ak < pivot1) { // Move a[k] to left part
+                    if (k != less) {
                         a[k] = a[less];
                         a[less] = ak;
                     }
                     less++;
-                } else { // a[k] > pivot
+                } 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
+                     * terminates, even though we don't test for it explicitly.
+                     * In other words, a[e3] acts as a sentinel for great.
+                     */
                     while (a[great] > pivot1) {
-                        if (k == great--) {
-                            break outer;
-                        }
+                        great--;
                     }
-                    a[k] = a[great];
-                    a[great--] = ak;
-
-                    if ((ak = a[k]) <  pivot1) {
+                    if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = ak;
+                        a[less++] = a[great];
+                        a[great--] = ak;
+                    } else { // a[great] == pivot1
+                        a[k] = pivot1;
+                        a[great--] = ak;
                     }
                 }
             }
@@ -535,26 +570,55 @@
         }
 
         /*
-         * If center part is too large (comprises > 5/6 of
-         * the array), swap internal pivot values to ends
+         * If center part is too large (comprises > 2/3 of the array),
+         * swap internal pivot values to ends
          */
-        if (less < e1 && e5 < great) {
+        if (less < e1 && great > e5) {
             while (a[less] == pivot1) {
                 less++;
             }
             while (a[great] == pivot2) {
                 great--;
             }
-            for (int k = less + 1; k <= 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) {
-                    a[k++] = a[less];
+                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;
-                } else if (ak == pivot2) {
-                    a[k] = a[great];
-                    a[great--] = pivot2;
-                } else {
-                    k++;
                 }
             }
         }
@@ -576,7 +640,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.
+     * the range to be sorted is empty (and the call is a no-op).
      *
      * @param a the array to be sorted
      * @param fromIndex the index of the first element, inclusive, to be sorted
@@ -606,13 +670,13 @@
     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 k = left + 1; k <= right; k++) {
-                short ak = a[k];
+            for (int i = left + 1; i <= right; i++) {
+                short ai = a[i];
                 int j;
-                for (j = k - 1; j >= left && ak < a[j]; j--) {
+                for (j = i - 1; j >= left && ai < a[j]; j--) {
                     a[j + 1] = a[j];
                 }
-                a[j + 1] = ak;
+                a[j + 1] = ai;
             }
         } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
             // Use counting sort on huge arrays
@@ -671,7 +735,7 @@
          * second terciles of the array. Note that pivot1 <= pivot2.
          *
          * The pivots are stored in local variables, and the first and
-         * the last of the sorted elements are moved to the locations
+         * 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.
@@ -679,27 +743,26 @@
         short pivot1 = ae2; a[e2] = a[left];
         short pivot2 = ae4; a[e4] = a[right];
 
-        /*
-         * Partitioning
-         *
-         *   left part         center part                  right part
-         * ------------------------------------------------------------
-         * [ < pivot1  |  pivot1 <= && <= pivot2  |   ?   |  > pivot2 ]
-         * ------------------------------------------------------------
-         *              ^                          ^     ^
-         *              |                          |     |
-         *             less                        k   great
-         */
-
         // 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
 
-        boolean pivotsDiffer = pivot1 != pivot2;
+        boolean pivotsDiffer = (pivot1 != pivot2);
 
         if (pivotsDiffer) {
             /*
+             * Partitioning:
+             *
+             *   left part         center part                    right part
+             * +------------------------------------------------------------+
+             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
+             * +------------------------------------------------------------+
+             *              ^                          ^       ^
+             *              |                          |       |
+             *             less                        k     great
+             *
              * Invariants:
+             *
              *              all in (left, less)   < pivot1
              *    pivot1 <= all in [less, k)     <= pivot2
              *              all in (great, right) > pivot2
@@ -709,37 +772,37 @@
             outer:
             for (int k = less; k <= great; k++) {
                 short ak = a[k];
-                if (ak < pivot1) {
-                    if (k > less) {
+                if (ak < pivot1) { // Move a[k] to left part
+                    if (k != less) {
                         a[k] = a[less];
                         a[less] = ak;
                     }
                     less++;
-                } else if (ak > pivot2) {
+                } else if (ak > pivot2) { // Move a[k] to right part
                     while (a[great] > pivot2) {
-                        if (k == great--) {
+                        if (great-- == k) {
                             break outer;
                         }
                     }
-                    a[k] = a[great];
-                    a[great--] = ak;
-
-                    if ((ak = a[k]) <  pivot1) {
+                    if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = ak;
+                        a[less++] = a[great];
+                        a[great--] = ak;
+                    } else { // pivot1 <= a[great] <= pivot2
+                        a[k] = a[great];
+                        a[great--] = ak;
                     }
                 }
             }
         } 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", partition:
              *
              *   left part   center part            right part
-             * -------------------------------------------------
-             * [  < pivot  |  == pivot  |    ?    |  > pivot   ]
-             * -------------------------------------------------
-             *
+             * +----------------------------------------------+
+             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
+             * +----------------------------------------------+
              *              ^            ^       ^
              *              |            |       |
              *             less          k     great
@@ -752,30 +815,34 @@
              *
              * Pointer k is the first index of ?-part
              */
-            outer:
             for (int k = less; k <= great; k++) {
                 short ak = a[k];
                 if (ak == pivot1) {
                     continue;
                 }
-                if (ak < pivot1) {
-                    if (k > less) {
+                if (ak < pivot1) { // Move a[k] to left part
+                    if (k != less) {
                         a[k] = a[less];
                         a[less] = ak;
                     }
                     less++;
-                } else { // a[k] > pivot
+                } 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
+                     * terminates, even though we don't test for it explicitly.
+                     * In other words, a[e3] acts as a sentinel for great.
+                     */
                     while (a[great] > pivot1) {
-                        if (k == great--) {
-                            break outer;
-                        }
+                        great--;
                     }
-                    a[k] = a[great];
-                    a[great--] = ak;
-
-                    if ((ak = a[k]) <  pivot1) {
+                    if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = ak;
+                        a[less++] = a[great];
+                        a[great--] = ak;
+                    } else { // a[great] == pivot1
+                        a[k] = pivot1;
+                        a[great--] = ak;
                     }
                 }
             }
@@ -798,26 +865,55 @@
         }
 
         /*
-         * If center part is too large (comprises > 5/6 of
-         * the array), swap internal pivot values to ends
+         * If center part is too large (comprises > 2/3 of the array),
+         * swap internal pivot values to ends
          */
-        if (less < e1 && e5 < great) {
+        if (less < e1 && great > e5) {
             while (a[less] == pivot1) {
                 less++;
             }
             while (a[great] == pivot2) {
                 great--;
             }
-            for (int k = less + 1; k <= 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) {
-                    a[k++] = a[less];
+                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;
-                } else if (ak == pivot2) {
-                    a[k] = a[great];
-                    a[great--] = pivot2;
-                } else {
-                    k++;
                 }
             }
         }
@@ -839,7 +935,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.
+     * the range to be sorted is empty (and the call is a no-op).
      *
      * @param a the array to be sorted
      * @param fromIndex the index of the first element, inclusive, to be sorted
@@ -869,13 +965,13 @@
     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 k = left + 1; k <= right; k++) {
-                char ak = a[k];
+            for (int i = left + 1; i <= right; i++) {
+                char ai = a[i];
                 int j;
-                for (j = k - 1; j >= left && ak < a[j]; j--) {
+                for (j = i - 1; j >= left && ai < a[j]; j--) {
                     a[j + 1] = a[j];
                 }
-                a[j + 1] = ak;
+                a[j + 1] = ai;
             }
         } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
             // Use counting sort on huge arrays
@@ -932,7 +1028,7 @@
          * second terciles of the array. Note that pivot1 <= pivot2.
          *
          * The pivots are stored in local variables, and the first and
-         * the last of the sorted elements are moved to the locations
+         * 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.
@@ -940,27 +1036,26 @@
         char pivot1 = ae2; a[e2] = a[left];
         char pivot2 = ae4; a[e4] = a[right];
 
-        /*
-         * Partitioning
-         *
-         *   left part         center part                  right part
-         * ------------------------------------------------------------
-         * [ < pivot1  |  pivot1 <= && <= pivot2  |   ?   |  > pivot2 ]
-         * ------------------------------------------------------------
-         *              ^                          ^     ^
-         *              |                          |     |
-         *             less                        k   great
-         */
-
         // 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
 
-        boolean pivotsDiffer = pivot1 != pivot2;
+        boolean pivotsDiffer = (pivot1 != pivot2);
 
         if (pivotsDiffer) {
             /*
+             * Partitioning:
+             *
+             *   left part         center part                    right part
+             * +------------------------------------------------------------+
+             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
+             * +------------------------------------------------------------+
+             *              ^                          ^       ^
+             *              |                          |       |
+             *             less                        k     great
+             *
              * Invariants:
+             *
              *              all in (left, less)   < pivot1
              *    pivot1 <= all in [less, k)     <= pivot2
              *              all in (great, right) > pivot2
@@ -970,37 +1065,37 @@
             outer:
             for (int k = less; k <= great; k++) {
                 char ak = a[k];
-                if (ak < pivot1) {
-                    if (k > less) {
+                if (ak < pivot1) { // Move a[k] to left part
+                    if (k != less) {
                         a[k] = a[less];
                         a[less] = ak;
                     }
                     less++;
-                } else if (ak > pivot2) {
+                } else if (ak > pivot2) { // Move a[k] to right part
                     while (a[great] > pivot2) {
-                        if (k == great--) {
+                        if (great-- == k) {
                             break outer;
                         }
                     }
-                    a[k] = a[great];
-                    a[great--] = ak;
-
-                    if ((ak = a[k]) <  pivot1) {
+                    if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = ak;
+                        a[less++] = a[great];
+                        a[great--] = ak;
+                    } else { // pivot1 <= a[great] <= pivot2
+                        a[k] = a[great];
+                        a[great--] = ak;
                     }
                 }
             }
         } 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", partition:
              *
              *   left part   center part            right part
-             * -------------------------------------------------
-             * [  < pivot  |  == pivot  |    ?    |  > pivot   ]
-             * -------------------------------------------------
-             *
+             * +----------------------------------------------+
+             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
+             * +----------------------------------------------+
              *              ^            ^       ^
              *              |            |       |
              *             less          k     great
@@ -1013,30 +1108,34 @@
              *
              * Pointer k is the first index of ?-part
              */
-            outer:
             for (int k = less; k <= great; k++) {
                 char ak = a[k];
                 if (ak == pivot1) {
                     continue;
                 }
-                if (ak < pivot1) {
-                    if (k > less) {
+                if (ak < pivot1) { // Move a[k] to left part
+                    if (k != less) {
                         a[k] = a[less];
                         a[less] = ak;
                     }
                     less++;
-                } else { // a[k] > pivot
+                } 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
+                     * terminates, even though we don't test for it explicitly.
+                     * In other words, a[e3] acts as a sentinel for great.
+                     */
                     while (a[great] > pivot1) {
-                        if (k == great--) {
-                            break outer;
-                        }
+                        great--;
                     }
-                    a[k] = a[great];
-                    a[great--] = ak;
-
-                    if ((ak = a[k]) <  pivot1) {
+                    if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = ak;
+                        a[less++] = a[great];
+                        a[great--] = ak;
+                    } else { // a[great] == pivot1
+                        a[k] = pivot1;
+                        a[great--] = ak;
                     }
                 }
             }
@@ -1059,26 +1158,55 @@
         }
 
         /*
-         * If center part is too large (comprises > 5/6 of
-         * the array), swap internal pivot values to ends
+         * If center part is too large (comprises > 2/3 of the array),
+         * swap internal pivot values to ends
          */
-        if (less < e1 && e5 < great) {
+        if (less < e1 && great > e5) {
             while (a[less] == pivot1) {
                 less++;
             }
             while (a[great] == pivot2) {
                 great--;
             }
-            for (int k = less + 1; k <= 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) {
-                    a[k++] = a[less];
+                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;
-                } else if (ak == pivot2) {
-                    a[k] = a[great];
-                    a[great--] = pivot2;
-                } else {
-                    k++;
                 }
             }
         }
@@ -1100,7 +1228,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.
+     * the range to be sorted is empty (and the call is a no-op).
      *
      * @param a the array to be sorted
      * @param fromIndex the index of the first element, inclusive, to be sorted
@@ -1130,13 +1258,13 @@
     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 k = left + 1; k <= right; k++) {
-                byte ak = a[k];
+            for (int i = left + 1; i <= right; i++) {
+                byte ai = a[i];
                 int j;
-                for (j = k - 1; j >= left && ak < a[j]; j--) {
+                for (j = i - 1; j >= left && ai < a[j]; j--) {
                     a[j + 1] = a[j];
                 }
-                a[j + 1] = ak;
+                a[j + 1] = ai;
             }
         } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
             // Use counting sort on huge arrays
@@ -1195,7 +1323,7 @@
          * second terciles of the array. Note that pivot1 <= pivot2.
          *
          * The pivots are stored in local variables, and the first and
-         * the last of the sorted elements are moved to the locations
+         * 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.
@@ -1203,27 +1331,26 @@
         byte pivot1 = ae2; a[e2] = a[left];
         byte pivot2 = ae4; a[e4] = a[right];
 
-        /*
-         * Partitioning
-         *
-         *   left part         center part                  right part
-         * ------------------------------------------------------------
-         * [ < pivot1  |  pivot1 <= && <= pivot2  |   ?   |  > pivot2 ]
-         * ------------------------------------------------------------
-         *              ^                          ^     ^
-         *              |                          |     |
-         *             less                        k   great
-         */
-
         // 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
 
-        boolean pivotsDiffer = pivot1 != pivot2;
+        boolean pivotsDiffer = (pivot1 != pivot2);
 
         if (pivotsDiffer) {
             /*
+             * Partitioning:
+             *
+             *   left part         center part                    right part
+             * +------------------------------------------------------------+
+             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
+             * +------------------------------------------------------------+
+             *              ^                          ^       ^
+             *              |                          |       |
+             *             less                        k     great
+             *
              * Invariants:
+             *
              *              all in (left, less)   < pivot1
              *    pivot1 <= all in [less, k)     <= pivot2
              *              all in (great, right) > pivot2
@@ -1233,37 +1360,37 @@
             outer:
             for (int k = less; k <= great; k++) {
                 byte ak = a[k];
-                if (ak < pivot1) {
-                    if (k > less) {
+                if (ak < pivot1) { // Move a[k] to left part
+                    if (k != less) {
                         a[k] = a[less];
                         a[less] = ak;
                     }
                     less++;
-                } else if (ak > pivot2) {
+                } else if (ak > pivot2) { // Move a[k] to right part
                     while (a[great] > pivot2) {
-                        if (k == great--) {
+                        if (great-- == k) {
                             break outer;
                         }
                     }
-                    a[k] = a[great];
-                    a[great--] = ak;
-
-                    if ((ak = a[k]) <  pivot1) {
+                    if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = ak;
+                        a[less++] = a[great];
+                        a[great--] = ak;
+                    } else { // pivot1 <= a[great] <= pivot2
+                        a[k] = a[great];
+                        a[great--] = ak;
                     }
                 }
             }
         } 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", partition:
              *
              *   left part   center part            right part
-             * -------------------------------------------------
-             * [  < pivot  |  == pivot  |    ?    |  > pivot   ]
-             * -------------------------------------------------
-             *
+             * +----------------------------------------------+
+             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
+             * +----------------------------------------------+
              *              ^            ^       ^
              *              |            |       |
              *             less          k     great
@@ -1276,30 +1403,34 @@
              *
              * Pointer k is the first index of ?-part
              */
-            outer:
             for (int k = less; k <= great; k++) {
                 byte ak = a[k];
                 if (ak == pivot1) {
                     continue;
                 }
-                if (ak < pivot1) {
-                    if (k > less) {
+                if (ak < pivot1) { // Move a[k] to left part
+                    if (k != less) {
                         a[k] = a[less];
                         a[less] = ak;
                     }
                     less++;
-                } else { // a[k] > pivot
+                } 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
+                     * terminates, even though we don't test for it explicitly.
+                     * In other words, a[e3] acts as a sentinel for great.
+                     */
                     while (a[great] > pivot1) {
-                        if (k == great--) {
-                            break outer;
-                        }
+                        great--;
                     }
-                    a[k] = a[great];
-                    a[great--] = ak;
-
-                    if ((ak = a[k]) <  pivot1) {
+                    if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = ak;
+                        a[less++] = a[great];
+                        a[great--] = ak;
+                    } else { // a[great] == pivot1
+                        a[k] = pivot1;
+                        a[great--] = ak;
                     }
                 }
             }
@@ -1322,26 +1453,55 @@
         }
 
         /*
-         * If center part is too large (comprises > 5/6 of
-         * the array), swap internal pivot values to ends
+         * If center part is too large (comprises > 2/3 of the array),
+         * swap internal pivot values to ends
          */
-        if (less < e1 && e5 < great) {
+        if (less < e1 && great > e5) {
             while (a[less] == pivot1) {
                 less++;
             }
             while (a[great] == pivot2) {
                 great--;
             }
-            for (int k = less + 1; k <= 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) {
-                    a[k++] = a[less];
+                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;
-                } else if (ak == pivot2) {
-                    a[k] = a[great];
-                    a[great--] = pivot2;
-                } else {
-                    k++;
                 }
             }
         }
@@ -1371,7 +1531,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.
+     * 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}
@@ -1485,13 +1645,13 @@
     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 k = left + 1; k <= right; k++) {
-                float ak = a[k];
+            for (int i = left + 1; i <= right; i++) {
+                float ai = a[i];
                 int j;
-                for (j = k - 1; j >= left && ak < a[j]; j--) {
+                for (j = i - 1; j >= left && ai < a[j]; j--) {
                     a[j + 1] = a[j];
                 }
-                a[j + 1] = ak;
+                a[j + 1] = ai;
             }
         } else { // Use Dual-Pivot Quicksort on large arrays
             dualPivotQuicksort(a, left, right);
@@ -1536,7 +1696,7 @@
          * second terciles of the array. Note that pivot1 <= pivot2.
          *
          * The pivots are stored in local variables, and the first and
-         * the last of the sorted elements are moved to the locations
+         * 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.
@@ -1544,27 +1704,26 @@
         float pivot1 = ae2; a[e2] = a[left];
         float pivot2 = ae4; a[e4] = a[right];
 
-        /*
-         * Partitioning
-         *
-         *   left part         center part                  right part
-         * ------------------------------------------------------------
-         * [ < pivot1  |  pivot1 <= && <= pivot2  |   ?   |  > pivot2 ]
-         * ------------------------------------------------------------
-         *              ^                          ^     ^
-         *              |                          |     |
-         *             less                        k   great
-         */
-
         // 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
 
-        boolean pivotsDiffer = pivot1 != pivot2;
+        boolean pivotsDiffer = (pivot1 != pivot2);
 
         if (pivotsDiffer) {
             /*
+             * Partitioning:
+             *
+             *   left part         center part                    right part
+             * +------------------------------------------------------------+
+             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
+             * +------------------------------------------------------------+
+             *              ^                          ^       ^
+             *              |                          |       |
+             *             less                        k     great
+             *
              * Invariants:
+             *
              *              all in (left, less)   < pivot1
              *    pivot1 <= all in [less, k)     <= pivot2
              *              all in (great, right) > pivot2
@@ -1574,37 +1733,37 @@
             outer:
             for (int k = less; k <= great; k++) {
                 float ak = a[k];
-                if (ak < pivot1) {
-                    if (k > less) {
+                if (ak < pivot1) { // Move a[k] to left part
+                    if (k != less) {
                         a[k] = a[less];
                         a[less] = ak;
                     }
                     less++;
-                } else if (ak > pivot2) {
+                } else if (ak > pivot2) { // Move a[k] to right part
                     while (a[great] > pivot2) {
-                        if (k == great--) {
+                        if (great-- == k) {
                             break outer;
                         }
                     }
-                    a[k] = a[great];
-                    a[great--] = ak;
-
-                    if ((ak = a[k]) <  pivot1) {
+                    if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = ak;
+                        a[less++] = a[great];
+                        a[great--] = ak;
+                    } else { // pivot1 <= a[great] <= pivot2
+                        a[k] = a[great];
+                        a[great--] = ak;
                     }
                 }
             }
         } 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", partition:
              *
              *   left part   center part            right part
-             * -------------------------------------------------
-             * [  < pivot  |  == pivot  |    ?    |  > pivot   ]
-             * -------------------------------------------------
-             *
+             * +----------------------------------------------+
+             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
+             * +----------------------------------------------+
              *              ^            ^       ^
              *              |            |       |
              *             less          k     great
@@ -1617,30 +1776,34 @@
              *
              * Pointer k is the first index of ?-part
              */
-            outer:
             for (int k = less; k <= great; k++) {
                 float ak = a[k];
                 if (ak == pivot1) {
                     continue;
                 }
-                if (ak < pivot1) {
-                    if (k > less) {
+                if (ak < pivot1) { // Move a[k] to left part
+                    if (k != less) {
                         a[k] = a[less];
                         a[less] = ak;
                     }
                     less++;
-                } else { // a[k] > pivot
+                } 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
+                     * terminates, even though we don't test for it explicitly.
+                     * In other words, a[e3] acts as a sentinel for great.
+                     */
                     while (a[great] > pivot1) {
-                        if (k == great--) {
-                            break outer;
-                        }
+                        great--;
                     }
-                    a[k] = a[great];
-                    a[great--] = ak;
-
-                    if ((ak = a[k]) <  pivot1) {
+                    if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = ak;
+                        a[less++] = a[great];
+                        a[great--] = ak;
+                    } else { // a[great] == pivot1
+                        a[k] = pivot1;
+                        a[great--] = ak;
                     }
                 }
             }
@@ -1663,26 +1826,55 @@
         }
 
         /*
-         * If center part is too large (comprises > 5/6 of
-         * the array), swap internal pivot values to ends
+         * If center part is too large (comprises > 2/3 of the array),
+         * swap internal pivot values to ends
          */
-        if (less < e1 && e5 < great) {
+        if (less < e1 && great > e5) {
             while (a[less] == pivot1) {
                 less++;
             }
             while (a[great] == pivot2) {
                 great--;
             }
-            for (int k = less + 1; k <= 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) {
-                    a[k++] = a[less];
+                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;
-                } else if (ak == pivot2) {
-                    a[k] = a[great];
-                    a[great--] = pivot2;
-                } else {
-                    k++;
                 }
             }
         }
@@ -1712,7 +1904,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.
+     * 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 double
      * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
@@ -1826,13 +2018,13 @@
     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 k = left + 1; k <= right; k++) {
-                double ak = a[k];
+            for (int i = left + 1; i <= right; i++) {
+                double ai = a[i];
                 int j;
-                for (j = k - 1; j >= left && ak < a[j]; j--) {
+                for (j = i - 1; j >= left && ai < a[j]; j--) {
                     a[j + 1] = a[j];
                 }
-                a[j + 1] = ak;
+                a[j + 1] = ai;
             }
         } else { // Use Dual-Pivot Quicksort on large arrays
             dualPivotQuicksort(a, left, right);
@@ -1877,7 +2069,7 @@
          * second terciles of the array. Note that pivot1 <= pivot2.
          *
          * The pivots are stored in local variables, and the first and
-         * the last of the sorted elements are moved to the locations
+         * 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.
@@ -1885,27 +2077,26 @@
         double pivot1 = ae2; a[e2] = a[left];
         double pivot2 = ae4; a[e4] = a[right];
 
-        /*
-         * Partitioning
-         *
-         *   left part         center part                  right part
-         * ------------------------------------------------------------
-         * [ < pivot1  |  pivot1 <= && <= pivot2  |   ?   |  > pivot2 ]
-         * ------------------------------------------------------------
-         *              ^                          ^     ^
-         *              |                          |     |
-         *             less                        k   great
-         */
-
         // 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
 
-        boolean pivotsDiffer = pivot1 != pivot2;
+        boolean pivotsDiffer = (pivot1 != pivot2);
 
         if (pivotsDiffer) {
             /*
+             * Partitioning:
+             *
+             *   left part         center part                    right part
+             * +------------------------------------------------------------+
+             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
+             * +------------------------------------------------------------+
+             *              ^                          ^       ^
+             *              |                          |       |
+             *             less                        k     great
+             *
              * Invariants:
+             *
              *              all in (left, less)   < pivot1
              *    pivot1 <= all in [less, k)     <= pivot2
              *              all in (great, right) > pivot2
@@ -1915,37 +2106,37 @@
             outer:
             for (int k = less; k <= great; k++) {
                 double ak = a[k];
-                if (ak < pivot1) {
-                    if (k > less) {
+                if (ak < pivot1) { // Move a[k] to left part
+                    if (k != less) {
                         a[k] = a[less];
                         a[less] = ak;
                     }
                     less++;
-                } else if (ak > pivot2) {
+                } else if (ak > pivot2) { // Move a[k] to right part
                     while (a[great] > pivot2) {
-                        if (k == great--) {
+                        if (great-- == k) {
                             break outer;
                         }
                     }
-                    a[k] = a[great];
-                    a[great--] = ak;
-
-                    if ((ak = a[k]) <  pivot1) {
+                    if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = ak;
+                        a[less++] = a[great];
+                        a[great--] = ak;
+                    } else { // pivot1 <= a[great] <= pivot2
+                        a[k] = a[great];
+                        a[great--] = ak;
                     }
                 }
             }
         } 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", partition:
              *
              *   left part   center part            right part
-             * -------------------------------------------------
-             * [  < pivot  |  == pivot  |    ?    |  > pivot   ]
-             * -------------------------------------------------
-             *
+             * +----------------------------------------------+
+             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
+             * +----------------------------------------------+
              *              ^            ^       ^
              *              |            |       |
              *             less          k     great
@@ -1958,30 +2149,34 @@
              *
              * Pointer k is the first index of ?-part
              */
-            outer:
             for (int k = less; k <= great; k++) {
                 double ak = a[k];
                 if (ak == pivot1) {
                     continue;
                 }
-                if (ak < pivot1) {
-                    if (k > less) {
+                if (ak < pivot1) { // Move a[k] to left part
+                    if (k != less) {
                         a[k] = a[less];
                         a[less] = ak;
                     }
                     less++;
-                } else { // a[k] > pivot
+                } 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
+                     * terminates, even though we don't test for it explicitly.
+                     * In other words, a[e3] acts as a sentinel for great.
+                     */
                     while (a[great] > pivot1) {
-                        if (k == great--) {
-                            break outer;
-                        }
+                        great--;
                     }
-                    a[k] = a[great];
-                    a[great--] = ak;
-
-                    if ((ak = a[k]) <  pivot1) {
+                    if (a[great] < pivot1) {
                         a[k] = a[less];
-                        a[less++] = ak;
+                        a[less++] = a[great];
+                        a[great--] = ak;
+                    } else { // a[great] == pivot1
+                        a[k] = pivot1;
+                        a[great--] = ak;
                     }
                 }
             }
@@ -2004,26 +2199,55 @@
         }
 
         /*
-         * If center part is too large (comprises > 5/6 of
-         * the array), swap internal pivot values to ends
+         * If center part is too large (comprises > 2/3 of the array),
+         * swap internal pivot values to ends
          */
-        if (less < e1 && e5 < great) {
+        if (less < e1 && great > e5) {
             while (a[less] == pivot1) {
                 less++;
             }
             while (a[great] == pivot2) {
                 great--;
             }
-            for (int k = less + 1; k <= 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) {
-                    a[k++] = a[less];
+                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;
-                } else if (ak == pivot2) {
-                    a[k] = a[great];
-                    a[great--] = pivot2;
-                } else {
-                    k++;
                 }
             }
         }