jdk-sandbox: comparison jdk/src/share/classes/java/util/DualPivotQuicksort.java

equal deleted inserted replaced

-:12d58d6de82f
+:1f9c2400b8c5
 *
 * @author Vladimir Yaroslavskiy
 * @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() {}
 /*
 * Tuning parameters.
 /**
 * 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
 * @param toIndex the index of the last element, exclusive, to be sorted
 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
 }
 /**
 * 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 right} index is inclusive, and it does no range checking
-* {@code left} or {@code right}.
+* 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
 * @param right the index of the last element, inclusive, to be sorted
 */
 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++) {
+for (int i = left + 1; i <= right; i++) {
-int ak = a[k];
+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);
 }
 }
 * 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 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.
 */
 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
 *
 * Pointer k is the first index of ?-part
 */
 outer:
 for (int k = less; k <= great; k++) {
 int ak = a[k];
-if (ak < pivot1) {
+if (ak < pivot1) { // Move a[k] to left part
-if (k > less) {
+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];
+if (a[great] < pivot1) {
-a[great--] = ak;
+a[k] = a[less];
+a[less++] = a[great];
-if ((ak = a[k]) < pivot1) {
+a[great--] = ak;
-a[k] = a[less];
+} else { // pivot1 <= a[great] <= pivot2
-a[less++] = ak;
+a[k] = a[great];
+a[great--] = ak;
 }
 }
 }
 } else { // Pivots are equal
 /*
-* Partition degenerates to the traditional 3-way
+* Partition degenerates to the traditional 3-way,
-* (or "Dutch National Flag") partition:
+* or "Dutch National Flag", partition:
 *
 *   left part   center part            right part
-* -------------------------------------------------
+* +----------------------------------------------+
-* [  < pivot  |  == pivot  |    ?    |  > pivot   ]
+* |  < pivot  |  == pivot  |    ?    |  > pivot  |
-* -------------------------------------------------
+* +----------------------------------------------+
-*
 *              ^            ^       ^
 *              |            |       |
 *             less          k     great
 *
 * Invariants:
 *
 *   all in (left, less)   < pivot
 *   all in [less, k)     == pivot
 *   all in (great, right) > pivot
+*
+* Pointer k is the first index of ?-part
+*/
+for (int k = less; k <= great; k++) {
+int ak = a[k];
+if (ak == pivot1) {
+continue;
+}
+if (ak < pivot1) { // Move a[k] to left part
+if (k != less) {
+a[k] = a[less];
+a[less] = ak;
+}
+less++;
+} 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) {
+great--;
+}
+if (a[great] < pivot1) {
+a[k] = a[less];
+a[less++] = a[great];
+a[great--] = ak;
+} else { // a[great] == pivot1
+a[k] = pivot1;
+a[great--] = ak;
+}
+}
+}
+}
+// 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 == pivot1) {
+if (ak == pivot2) { // Move a[k] to right part
-continue;
+while (a[great] == pivot2) {
-}
+if (great-- == k) {
-if (ak < pivot1) {
-if (k > less) {
-a[k] = a[less];
-a[less] = ak;
-}
-less++;
-} else { // a[k] > pivot
-while (a[great] > pivot1) {
-if (k == great--) {
 break outer;
 }
 }
-a[k] = a[great];
+if (a[great] == pivot1) {
-a[great--] = ak;
+a[k] = a[less];
+a[less++] = pivot1;
-if ((ak = a[k]) <  pivot1) {
+} else { // pivot1 < a[great] < pivot2
-a[k] = a[less];
+a[k] = a[great];
-a[less++] = ak;
+}
-}
+a[great--] = pivot2;
-}
+} else if (ak == pivot1) { // Move a[k] to left part
-}
+a[k] = a[less];
-}
-// 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 > 5/6 of
-* the array), swap internal pivot values to ends
-*/
-if (less < e1 && e5 < great) {
-while (a[less] == pivot1) {
-less++;
-}
-while (a[great] == pivot2) {
-great--;
-}
-for (int k = less + 1; k <= great; ) {
-int ak = a[k];
-if (ak == pivot1) {
-a[k++] = a[less];
 a[less++] = pivot1;
-} else if (ak == pivot2) {
-a[k] = a[great];
-a[great--] = pivot2;
-} else {
-k++;
 }
 }
 }
 // Sort center part recursively, excluding known pivot values
 /**
 * 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
 * @param toIndex the index of the last element, exclusive, to be sorted
 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
 * @param right the index of the last element, inclusive, to be sorted
 */
 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++) {
+for (int i = left + 1; i <= right; i++) {
-long ak = a[k];
+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);
 }
 }
 * 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 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.
 */
 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
 *
 * Pointer k is the first index of ?-part
 */
 outer:
 for (int k = less; k <= great; k++) {
 long ak = a[k];
-if (ak < pivot1) {
+if (ak < pivot1) { // Move a[k] to left part
-if (k > less) {
+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];
+if (a[great] < pivot1) {
-a[great--] = ak;
+a[k] = a[less];
+a[less++] = a[great];
-if ((ak = a[k]) <  pivot1) {
+a[great--] = ak;
-a[k] = a[less];
+} else { // pivot1 <= a[great] <= pivot2
-a[less++] = ak;
+a[k] = a[great];
+a[great--] = ak;
 }
 }
 }
 } else { // Pivots are equal
 /*
-* Partition degenerates to the traditional 3-way
+* Partition degenerates to the traditional 3-way,
-* (or "Dutch National Flag") partition:
+* or "Dutch National Flag", partition:
 *
 *   left part   center part            right part
-* -------------------------------------------------
+* +----------------------------------------------+
-* [  < pivot  |  == pivot  |    ?    |  > pivot   ]
+* |  < pivot  |  == pivot  |    ?    |  > pivot  |
-* -------------------------------------------------
+* +----------------------------------------------+
-*
 *              ^            ^       ^
 *              |            |       |
 *             less          k     great
 *
 * Invariants:
 *
 *   all in (left, less)   < pivot
 *   all in [less, k)     == pivot
 *   all in (great, right) > pivot
+*
+* Pointer k is the first index of ?-part
+*/
+for (int k = less; k <= great; k++) {
+long ak = a[k];
+if (ak == pivot1) {
+continue;
+}
+if (ak < pivot1) { // Move a[k] to left part
+if (k != less) {
+a[k] = a[less];
+a[less] = ak;
+}
+less++;
+} 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) {
+great--;
+}
+if (a[great] < pivot1) {
+a[k] = a[less];
+a[less++] = a[great];
+a[great--] = ak;
+} else { // a[great] == pivot1
+a[k] = pivot1;
+a[great--] = ak;
+}
+}
+}
+}
+// 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 == pivot1) {
+if (ak == pivot2) { // Move a[k] to right part
-continue;
+while (a[great] == pivot2) {
-}
+if (great-- == k) {
-if (ak < pivot1) {
-if (k > less) {
-a[k] = a[less];
-a[less] = ak;
-}
-less++;
-} else { // a[k] > pivot
-while (a[great] > pivot1) {
-if (k == great--) {
 break outer;
 }
 }
-a[k] = a[great];
+if (a[great] == pivot1) {
-a[great--] = ak;
+a[k] = a[less];
+a[less++] = pivot1;
-if ((ak = a[k]) <  pivot1) {
+} else { // pivot1 < a[great] < pivot2
-a[k] = a[less];
+a[k] = a[great];
-a[less++] = ak;
+}
-}
+a[great--] = pivot2;
-}
+} else if (ak == pivot1) { // Move a[k] to left part
-}
+a[k] = a[less];
-}
-// 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 > 5/6 of
-* the array), swap internal pivot values to ends
-*/
-if (less < e1 && e5 < great) {
-while (a[less] == pivot1) {
-less++;
-}
-while (a[great] == pivot2) {
-great--;
-}
-for (int k = less + 1; k <= great; ) {
-long ak = a[k];
-if (ak == pivot1) {
-a[k++] = a[less];
 a[less++] = pivot1;
-} else if (ak == pivot2) {
-a[k] = a[great];
-a[great--] = pivot2;
-} else {
-k++;
 }
 }
 }
 // Sort center part recursively, excluding known pivot values
 /**
 * 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
 * @param toIndex the index of the last element, exclusive, to be sorted
 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
 * @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 k = left + 1; k <= right; k++) {
+for (int i = left + 1; i <= right; i++) {
-short ak = a[k];
+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
 int[] count = new int[NUM_SHORT_VALUES];
 * 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 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.
 */
 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
 *
 * Pointer k is the first index of ?-part
 */
 outer:
 for (int k = less; k <= great; k++) {
 short ak = a[k];
-if (ak < pivot1) {
+if (ak < pivot1) { // Move a[k] to left part
-if (k > less) {
+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];
+if (a[great] < pivot1) {
-a[great--] = ak;
+a[k] = a[less];
+a[less++] = a[great];
-if ((ak = a[k]) <  pivot1) {
+a[great--] = ak;
-a[k] = a[less];
+} else { // pivot1 <= a[great] <= pivot2
-a[less++] = ak;
+a[k] = a[great];
+a[great--] = ak;
 }
 }
 }
 } else { // Pivots are equal
 /*
-* Partition degenerates to the traditional 3-way
+* Partition degenerates to the traditional 3-way,
-* (or "Dutch National Flag") partition:
+* or "Dutch National Flag", partition:
 *
 *   left part   center part            right part
-* -------------------------------------------------
+* +----------------------------------------------+
-* [  < pivot  |  == pivot  |    ?    |  > pivot   ]
+* |  < pivot  |  == pivot  |    ?    |  > pivot  |
-* -------------------------------------------------
+* +----------------------------------------------+
-*
 *              ^            ^       ^
 *              |            |       |
 *             less          k     great
 *
 * Invariants:
 *
 *   all in (left, less)   < pivot
 *   all in [less, k)     == pivot
 *   all in (great, right) > pivot
+*
+* Pointer k is the first index of ?-part
+*/
+for (int k = less; k <= great; k++) {
+short ak = a[k];
+if (ak == pivot1) {
+continue;
+}
+if (ak < pivot1) { // Move a[k] to left part
+if (k != less) {
+a[k] = a[less];
+a[less] = ak;
+}
+less++;
+} 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) {
+great--;
+}
+if (a[great] < pivot1) {
+a[k] = a[less];
+a[less++] = a[great];
+a[great--] = ak;
+} else { // a[great] == pivot1
+a[k] = pivot1;
+a[great--] = ak;
+}
+}
+}
+}
+// 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 == pivot1) {
+if (ak == pivot2) { // Move a[k] to right part
-continue;
+while (a[great] == pivot2) {
-}
+if (great-- == k) {
-if (ak < pivot1) {
-if (k > less) {
-a[k] = a[less];
-a[less] = ak;
-}
-less++;
-} else { // a[k] > pivot
-while (a[great] > pivot1) {
-if (k == great--) {
 break outer;
 }
 }
-a[k] = a[great];
+if (a[great] == pivot1) {
-a[great--] = ak;
+a[k] = a[less];
+a[less++] = pivot1;
-if ((ak = a[k]) <  pivot1) {
+} else { // pivot1 < a[great] < pivot2
-a[k] = a[less];
+a[k] = a[great];
-a[less++] = ak;
+}
-}
+a[great--] = pivot2;
-}
+} else if (ak == pivot1) { // Move a[k] to left part
-}
+a[k] = a[less];
-}
-// 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 > 5/6 of
-* the array), swap internal pivot values to ends
-*/
-if (less < e1 && e5 < great) {
-while (a[less] == pivot1) {
-less++;
-}
-while (a[great] == pivot2) {
-great--;
-}
-for (int k = less + 1; k <= great; ) {
-short ak = a[k];
-if (ak == pivot1) {
-a[k++] = a[less];
 a[less++] = pivot1;
-} else if (ak == pivot2) {
-a[k] = a[great];
-a[great--] = pivot2;
-} else {
-k++;
 }
 }
 }
 // Sort center part recursively, excluding known pivot values
 /**
 * 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
 * @param toIndex the index of the last element, exclusive, to be sorted
 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
 * @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 k = left + 1; k <= right; k++) {
+for (int i = left + 1; i <= right; i++) {
-char ak = a[k];
+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
 int[] count = new int[NUM_CHAR_VALUES];
 * 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 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.
 */
 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
 *
 * Pointer k is the first index of ?-part
 */
 outer:
 for (int k = less; k <= great; k++) {
 char ak = a[k];
-if (ak < pivot1) {
+if (ak < pivot1) { // Move a[k] to left part
-if (k > less) {
+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];
+if (a[great] < pivot1) {
-a[great--] = ak;
+a[k] = a[less];
+a[less++] = a[great];
-if ((ak = a[k]) <  pivot1) {
+a[great--] = ak;
-a[k] = a[less];
+} else { // pivot1 <= a[great] <= pivot2
-a[less++] = ak;
+a[k] = a[great];
+a[great--] = ak;
 }
 }
 }
 } else { // Pivots are equal
 /*
-* Partition degenerates to the traditional 3-way
+* Partition degenerates to the traditional 3-way,
-* (or "Dutch National Flag") partition:
+* or "Dutch National Flag", partition:
 *
 *   left part   center part            right part
-* -------------------------------------------------
+* +----------------------------------------------+
-* [  < pivot  |  == pivot  |    ?    |  > pivot   ]
+* |  < pivot  |  == pivot  |    ?    |  > pivot  |
-* -------------------------------------------------
+* +----------------------------------------------+
-*
 *              ^            ^       ^
 *              |            |       |
 *             less          k     great
 *
 * Invariants:
 *
 *   all in (left, less)   < pivot
 *   all in [less, k)     == pivot
 *   all in (great, right) > pivot
+*
+* Pointer k is the first index of ?-part
+*/
+for (int k = less; k <= great; k++) {
+char ak = a[k];
+if (ak == pivot1) {
+continue;
+}
+if (ak < pivot1) { // Move a[k] to left part
+if (k != less) {
+a[k] = a[less];
+a[less] = ak;
+}
+less++;
+} 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) {
+great--;
+}
+if (a[great] < pivot1) {
+a[k] = a[less];
+a[less++] = a[great];
+a[great--] = ak;
+} else { // a[great] == pivot1
+a[k] = pivot1;
+a[great--] = ak;
+}
+}
+}
+}
+// 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 == pivot1) {
+if (ak == pivot2) { // Move a[k] to right part
-continue;
+while (a[great] == pivot2) {
-}
+if (great-- == k) {
-if (ak < pivot1) {
-if (k > less) {
-a[k] = a[less];
-a[less] = ak;
-}
-less++;
-} else { // a[k] > pivot
-while (a[great] > pivot1) {
-if (k == great--) {
 break outer;
 }
 }
-a[k] = a[great];
+if (a[great] == pivot1) {
-a[great--] = ak;
+a[k] = a[less];
+a[less++] = pivot1;
-if ((ak = a[k]) <  pivot1) {
+} else { // pivot1 < a[great] < pivot2
-a[k] = a[less];
+a[k] = a[great];
-a[less++] = ak;
+}
-}
+a[great--] = pivot2;
-}
+} else if (ak == pivot1) { // Move a[k] to left part
-}
+a[k] = a[less];
-}
-// 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 > 5/6 of
-* the array), swap internal pivot values to ends
-*/
-if (less < e1 && e5 < great) {
-while (a[less] == pivot1) {
-less++;
-}
-while (a[great] == pivot2) {
-great--;
-}
-for (int k = less + 1; k <= great; ) {
-char ak = a[k];
-if (ak == pivot1) {
-a[k++] = a[less];
 a[less++] = pivot1;
-} else if (ak == pivot2) {
-a[k] = a[great];
-a[great--] = pivot2;
-} else {
-k++;
 }
 }
 }
 // Sort center part recursively, excluding known pivot values
 /**
 * 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
 * @param toIndex the index of the last element, exclusive, to be sorted
 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
 * @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 k = left + 1; k <= right; k++) {
+for (int i = left + 1; i <= right; i++) {
-byte ak = a[k];
+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
 int[] count = new int[NUM_BYTE_VALUES];
 * 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 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.
 */
 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
 *
 * Pointer k is the first index of ?-part
 */
 outer:
 for (int k = less; k <= great; k++) {
 byte ak = a[k];
-if (ak < pivot1) {
+if (ak < pivot1) { // Move a[k] to left part
-if (k > less) {
+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];
+if (a[great] < pivot1) {
-a[great--] = ak;
+a[k] = a[less];
+a[less++] = a[great];
-if ((ak = a[k]) <  pivot1) {
+a[great--] = ak;
-a[k] = a[less];
+} else { // pivot1 <= a[great] <= pivot2
-a[less++] = ak;
+a[k] = a[great];
+a[great--] = ak;
 }
 }
 }
 } else { // Pivots are equal
 /*
-* Partition degenerates to the traditional 3-way
+* Partition degenerates to the traditional 3-way,
-* (or "Dutch National Flag") partition:
+* or "Dutch National Flag", partition:
 *
 *   left part   center part            right part
-* -------------------------------------------------
+* +----------------------------------------------+
-* [  < pivot  |  == pivot  |    ?    |  > pivot   ]
+* |  < pivot  |  == pivot  |    ?    |  > pivot  |
-* -------------------------------------------------
+* +----------------------------------------------+
-*
 *              ^            ^       ^
 *              |            |       |
 *             less          k     great
 *
 * Invariants:
 *
 *   all in (left, less)   < pivot
 *   all in [less, k)     == pivot
 *   all in (great, right) > pivot
+*
+* Pointer k is the first index of ?-part
+*/
+for (int k = less; k <= great; k++) {
+byte ak = a[k];
+if (ak == pivot1) {
+continue;
+}
+if (ak < pivot1) { // Move a[k] to left part
+if (k != less) {
+a[k] = a[less];
+a[less] = ak;
+}
+less++;
+} 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) {
+great--;
+}
+if (a[great] < pivot1) {
+a[k] = a[less];
+a[less++] = a[great];
+a[great--] = ak;
+} else { // a[great] == pivot1
+a[k] = pivot1;
+a[great--] = ak;
+}
+}
+}
+}
+// 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 == pivot1) {
+if (ak == pivot2) { // Move a[k] to right part
-continue;
+while (a[great] == pivot2) {
-}
+if (great-- == k) {
-if (ak < pivot1) {
-if (k > less) {
-a[k] = a[less];
-a[less] = ak;
-}
-less++;
-} else { // a[k] > pivot
-while (a[great] > pivot1) {
-if (k == great--) {
 break outer;
 }
 }
-a[k] = a[great];
+if (a[great] == pivot1) {
-a[great--] = ak;
+a[k] = a[less];
+a[less++] = pivot1;
-if ((ak = a[k]) <  pivot1) {
+} else { // pivot1 < a[great] < pivot2
-a[k] = a[less];
+a[k] = a[great];
-a[less++] = ak;
+}
-}
+a[great--] = pivot2;
-}
+} else if (ak == pivot1) { // Move a[k] to left part
-}
+a[k] = a[less];
-}
-// 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 > 5/6 of
-* the array), swap internal pivot values to ends
-*/
-if (less < e1 && e5 < great) {
-while (a[less] == pivot1) {
-less++;
-}
-while (a[great] == pivot2) {
-great--;
-}
-for (int k = less + 1; k <= great; ) {
-byte ak = a[k];
-if (ak == pivot1) {
-a[k++] = a[less];
 a[less++] = pivot1;
-} else if (ak == pivot2) {
-a[k] = a[great];
-a[great--] = pivot2;
-} else {
-k++;
 }
 }
 }
 // Sort center part recursively, excluding known pivot values
 /**
 * 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}
 * value compares neither less than, greater than, nor equal to any value,
 * even itself. This method uses the total order imposed by the method
 * @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 k = left + 1; k <= right; k++) {
+for (int i = left + 1; i <= right; i++) {
-float ak = a[k];
+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);
 }
 }
 * 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 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.
 */
 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
 *
 * Pointer k is the first index of ?-part
 */
 outer:
 for (int k = less; k <= great; k++) {
 float ak = a[k];
-if (ak < pivot1) {
+if (ak < pivot1) { // Move a[k] to left part
-if (k > less) {
+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];
+if (a[great] < pivot1) {
-a[great--] = ak;
+a[k] = a[less];
+a[less++] = a[great];
-if ((ak = a[k]) <  pivot1) {
+a[great--] = ak;
-a[k] = a[less];
+} else { // pivot1 <= a[great] <= pivot2
-a[less++] = ak;
+a[k] = a[great];
+a[great--] = ak;
 }
 }
 }
 } else { // Pivots are equal
 /*
-* Partition degenerates to the traditional 3-way
+* Partition degenerates to the traditional 3-way,
-* (or "Dutch National Flag") partition:
+* or "Dutch National Flag", partition:
 *
 *   left part   center part            right part
-* -------------------------------------------------
+* +----------------------------------------------+
-* [  < pivot  |  == pivot  |    ?    |  > pivot   ]
+* |  < pivot  |  == pivot  |    ?    |  > pivot  |
-* -------------------------------------------------
+* +----------------------------------------------+
-*
 *              ^            ^       ^
 *              |            |       |
 *             less          k     great
 *
 * Invariants:
 *
 *   all in (left, less)   < pivot
 *   all in [less, k)     == pivot
 *   all in (great, right) > pivot
+*
+* Pointer k is the first index of ?-part
+*/
+for (int k = less; k <= great; k++) {
+float ak = a[k];
+if (ak == pivot1) {
+continue;
+}
+if (ak < pivot1) { // Move a[k] to left part
+if (k != less) {
+a[k] = a[less];
+a[less] = ak;
+}
+less++;
+} 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) {
+great--;
+}
+if (a[great] < pivot1) {
+a[k] = a[less];
+a[less++] = a[great];
+a[great--] = ak;
+} else { // a[great] == pivot1
+a[k] = pivot1;
+a[great--] = ak;
+}
+}
+}
+}
+// 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 == pivot1) {
+if (ak == pivot2) { // Move a[k] to right part
-continue;
+while (a[great] == pivot2) {
-}
+if (great-- == k) {
-if (ak < pivot1) {
-if (k > less) {
-a[k] = a[less];
-a[less] = ak;
-}
-less++;
-} else { // a[k] > pivot
-while (a[great] > pivot1) {
-if (k == great--) {
 break outer;
 }
 }
-a[k] = a[great];
+if (a[great] == pivot1) {
-a[great--] = ak;
+a[k] = a[less];
+a[less++] = pivot1;
-if ((ak = a[k]) <  pivot1) {
+} else { // pivot1 < a[great] < pivot2
-a[k] = a[less];
+a[k] = a[great];
-a[less++] = ak;
+}
-}
+a[great--] = pivot2;
-}
+} else if (ak == pivot1) { // Move a[k] to left part
-}
+a[k] = a[less];
-}
-// 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 > 5/6 of
-* the array), swap internal pivot values to ends
-*/
-if (less < e1 && e5 < great) {
-while (a[less] == pivot1) {
-less++;
-}
-while (a[great] == pivot2) {
-great--;
-}
-for (int k = less + 1; k <= great; ) {
-float ak = a[k];
-if (ak == pivot1) {
-a[k++] = a[less];
 a[less++] = pivot1;
-} else if (ak == pivot2) {
-a[k] = a[great];
-a[great--] = pivot2;
-} else {
-k++;
 }
 }
 }
 // Sort center part recursively, excluding known pivot values
 /**
 * 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}
 * value compares neither less than, greater than, nor equal to any value,
 * even itself. This method uses the total order imposed by the method
 * @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 k = left + 1; k <= right; k++) {
+for (int i = left + 1; i <= right; i++) {
-double ak = a[k];
+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);
 }
 }
 * 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 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.
 */
 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
 *
 * Pointer k is the first index of ?-part
 */
 outer:
 for (int k = less; k <= great; k++) {
 double ak = a[k];
-if (ak < pivot1) {
+if (ak < pivot1) { // Move a[k] to left part
-if (k > less) {
+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];
+if (a[great] < pivot1) {
-a[great--] = ak;
+a[k] = a[less];
+a[less++] = a[great];
-if ((ak = a[k]) <  pivot1) {
+a[great--] = ak;
-a[k] = a[less];
+} else { // pivot1 <= a[great] <= pivot2
-a[less++] = ak;
+a[k] = a[great];
+a[great--] = ak;
 }
 }
 }
 } else { // Pivots are equal
 /*
-* Partition degenerates to the traditional 3-way
+* Partition degenerates to the traditional 3-way,
-* (or "Dutch National Flag") partition:
+* or "Dutch National Flag", partition:
 *
 *   left part   center part            right part
-* -------------------------------------------------
+* +----------------------------------------------+
-* [  < pivot  |  == pivot  |    ?    |  > pivot   ]
+* |  < pivot  |  == pivot  |    ?    |  > pivot  |
-* -------------------------------------------------
+* +----------------------------------------------+
-*
 *              ^            ^       ^
 *              |            |       |
 *             less          k     great
 *
 * Invariants:
 *
 *   all in (left, less)   < pivot
 *   all in [less, k)     == pivot
 *   all in (great, right) > pivot
+*
+* Pointer k is the first index of ?-part
+*/
+for (int k = less; k <= great; k++) {
+double ak = a[k];
+if (ak == pivot1) {
+continue;
+}
+if (ak < pivot1) { // Move a[k] to left part
+if (k != less) {
+a[k] = a[less];
+a[less] = ak;
+}
+less++;
+} 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) {
+great--;
+}
+if (a[great] < pivot1) {
+a[k] = a[less];
+a[less++] = a[great];
+a[great--] = ak;
+} else { // a[great] == pivot1
+a[k] = pivot1;
+a[great--] = ak;
+}
+}
+}
+}
+// 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 == pivot1) {
+if (ak == pivot2) { // Move a[k] to right part
-continue;
+while (a[great] == pivot2) {
-}
+if (great-- == k) {
-if (ak < pivot1) {
-if (k > less) {
-a[k] = a[less];
-a[less] = ak;
-}
-less++;
-} else { // a[k] > pivot
-while (a[great] > pivot1) {
-if (k == great--) {
 break outer;
 }
 }
-a[k] = a[great];
+if (a[great] == pivot1) {
-a[great--] = ak;
+a[k] = a[less];
+a[less++] = pivot1;
-if ((ak = a[k]) <  pivot1) {
+} else { // pivot1 < a[great] < pivot2
-a[k] = a[less];
+a[k] = a[great];
-a[less++] = ak;
+}
-}
+a[great--] = pivot2;
-}
+} else if (ak == pivot1) { // Move a[k] to left part
-}
+a[k] = a[less];
-}
-// 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 > 5/6 of
-* the array), swap internal pivot values to ends
-*/
-if (less < e1 && e5 < great) {
-while (a[less] == pivot1) {
-less++;
-}
-while (a[great] == pivot2) {
-great--;
-}
-for (int k = less + 1; k <= great; ) {
-double ak = a[k];
-if (ak == pivot1) {
-a[k++] = a[less];
 a[less++] = pivot1;
-} else if (ak == pivot2) {
-a[k] = a[great];
-a[great--] = pivot2;
-} else {
-k++;
 }
 }
 }
 // Sort center part recursively, excluding known pivot values

changeset 4356	1f9c2400b8c5
parent 4241	7d4f50f3806c
child 4980	bbfb5ddd9e58