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

equal deleted inserted replaced

-:cbd5448015d8
+:b90884cf34f5
 *
 * @author Vladimir Yaroslavskiy
 * @author Jon Bentley
 * @author Josh Bloch
 *
-* @version 2010.10.13 m765.827.12i:5\7p
+* @version 2011.01.21 m765.827.12i:5\7pm
 * @since 1.7
 */
 final class DualPivotQuicksort {
 /**
 private DualPivotQuicksort() {}
 /*
 * Tuning parameters.
 */
+/**
+* The maximum number of runs in merge sort.
+*/
+private static final int MAX_RUN_COUNT = 67;
+/**
+* The maximum length of run in merge sort.
+*/
+private static final int MAX_RUN_LENGTH = 33;
+/**
+* If the length of an array to be sorted is less than this
+* constant, Quicksort is used in preference to merge sort.
+*/
+private static final int QUICKSORT_THRESHOLD = 286;
 /**
 * If the length of an array to be sorted is less than this
 * constant, insertion sort is used in preference to Quicksort.
 */
 * Sorts the specified array.
 *
 * @param a the array to be sorted
 */
 public static void sort(int[] a) {
-sort(a, 0, a.length - 1, true);
+sort(a, 0, a.length - 1);
 }
 /**
 * Sorts the specified range of the array.
 *
 * @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
 */
 public static void sort(int[] a, int left, int right) {
-sort(a, left, right, true);
+// Use Quicksort on small arrays
+if (right - left < QUICKSORT_THRESHOLD) {
+sort(a, left, right, true);
+return;
+}
+/*
+* Index run[i] is the start of i-th run
+* (ascending or descending sequence).
+*/
+int[] run = new int[MAX_RUN_COUNT];
+int count = 0; run[0] = left;
+// Check if the array is nearly sorted
+for (int k = left; k < right; run[count] = k) {
+if (a[k] < a[k + 1]) { // ascending
+while (++k <= right && a[k - 1] <= a[k]);
+} else if (a[k] > a[k + 1]) { // descending
+while (++k <= right && a[k - 1] >= a[k]);
+for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
+int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
+}
+} else { // equal
+for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
+if (--m == 0) {
+sort(a, left, right, true);
+return;
+}
+}
+}
+/*
+* The array is not highly structured,
+* use Quicksort instead of merge sort.
+*/
+if (++count == MAX_RUN_COUNT) {
+sort(a, left, right, true);
+return;
+}
+}
+// Check special cases
+if (run[count] == right++) { // The last run contains one element
+run[++count] = right;
+} else if (count == 1) { // The array is already sorted
+return;
+}
+/*
+* Create temporary array, which is used for merging.
+* Implementation note: variable "right" is increased by 1.
+*/
+int[] b; byte odd = 0;
+for (int n = 1; (n <<= 1) < count; odd ^= 1);
+if (odd == 0) {
+b = a; a = new int[b.length];
+for (int i = left - 1; ++i < right; a[i] = b[i]);
+} else {
+b = new int[a.length];
+}
+// Merging
+for (int last; count > 1; count = last) {
+for (int k = (last = 0) + 2; k <= count; k += 2) {
+int hi = run[k], mi = run[k - 1];
+for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
+if (q >= hi || p < mi && a[p] <= a[q]) {
+b[i] = a[p++];
+} else {
+b[i] = a[q++];
+}
+}
+run[++last] = hi;
+}
+if ((count & 1) != 0) {
+for (int i = right, lo = run[count - 1]; --i >= lo;
+b[i] = a[i]
+);
+run[++last] = right;
+}
+int[] t = a; a = b; b = t;
+}
 }
 /**
 * Sorts the specified range of the array by Dual-Pivot Quicksort.
 *
 * @param leftmost indicates if this part is the leftmost in the range
 */
 private static void sort(int[] a, int left, int right, boolean leftmost) {
 int length = right - left + 1;
-// Use insertion sort on small arrays
+// Use insertion sort on tiny arrays
 if (length < INSERTION_SORT_THRESHOLD) {
 if (leftmost) {
 /*
 * Traditional (without sentinel) insertion sort,
 * optimized for server VM, is used in case of
 } else {
 /*
 * Skip the longest ascending sequence.
 */
 do {
-if (left++ >= right) {
+if (left >= right) {
 return;
 }
-} while (a[left - 1] <= a[left]);
+} while (a[++left] >= a[left - 1]);
 /*
 * Every element from adjoining part plays the role
 * of sentinel, therefore this allows us to avoid the
 * left range check on each iteration. Moreover, we use
-* the best improved algorithm, so called pair insertion
+* the more optimized algorithm, so called pair insertion
-* sort, which is faster than traditional implementation
+* sort, which is faster (in the context of Quicksort)
-* in the context of Dual-Pivot Quicksort.
+* than traditional implementation of insertion sort.
 */
-for (int k = left--; (left += 2) <= right; ) {
+for (int k = left; ++left <= right; k = ++left) {
-int a1, a2; k = left - 1;
+int a1 = a[k], a2 = a[left];
-if (a[k] < a[left]) {
+if (a1 < a2) {
-a2 = a[k]; a1 = a[left];
+a2 = a1; a1 = a[left];
-} else {
-a1 = a[k]; a2 = a[left];
 }
 while (a1 < a[--k]) {
 a[k + 2] = a[k];
 }
 a[++k + 1] = a1;
 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 }
 }
 }
-/*
-* Use the second and fourth of the five sorted elements as pivots.
-* These values are inexpensive approximations of the first and
-* second terciles of the array. Note that pivot1 <= pivot2.
-*/
-int pivot1 = a[e2];
-int pivot2 = a[e4];
 // Pointers
 int less  = left;  // The index of the first element of center part
 int great = right; // The index before the first element of right part
-if (pivot1 != pivot2) {
+if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
+/*
+* 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.
+*/
+int pivot1 = a[e2];
+int pivot2 = a[e4];
 /*
 * The first and the last elements to be sorted are moved to the
 * locations formerly occupied by the pivots. When partitioning
 * is complete, the pivots are swapped back into their final
 * positions, and excluded from subsequent sorting.
 /*
 * Here and below we use "a[i] = b; i++;" instead
 * of "a[i++] = b;" due to performance issue.
 */
 a[less] = ak;
-less++;
+++less;
 } else if (ak > pivot2) { // Move a[k] to right part
 while (a[great] > pivot2) {
 if (great-- == k) {
 break outer;
 }
 }
 if (a[great] < pivot1) { // a[great] <= pivot2
 a[k] = a[less];
 a[less] = a[great];
-less++;
+++less;
 } else { // pivot1 <= a[great] <= pivot2
 a[k] = a[great];
 }
 /*
 * Here and below we use "a[i] = b; i--;" instead
 * of "a[i--] = b;" due to performance issue.
 */
 a[great] = ak;
-great--;
+--great;
 }
 }
 // Swap pivots into their final positions
 a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
 if (less < e1 && e5 < great) {
 /*
 * Skip elements, which are equal to pivot values.
 */
 while (a[less] == pivot1) {
-less++;
+++less;
 }
 while (a[great] == pivot2) {
-great--;
+--great;
 }
 /*
 * Partitioning:
 *
 for (int k = less - 1; ++k <= great; ) {
 int ak = a[k];
 if (ak == pivot1) { // Move a[k] to left part
 a[k] = a[less];
 a[less] = ak;
-less++;
+++less;
 } else if (ak == pivot2) { // Move a[k] to right part
 while (a[great] == pivot2) {
 if (great-- == k) {
 break outer;
 }
 * of different signs. Therefore in float and
 * double sorting methods we have to use more
 * accurate assignment a[less] = a[great].
 */
 a[less] = pivot1;
-less++;
+++less;
 } else { // pivot1 < a[great] < pivot2
 a[k] = a[great];
 }
 a[great] = ak;
-great--;
+--great;
 }
 }
 }
 // Sort center part recursively
 sort(a, less, great, false);
-} else { // Pivots are equal
+} else { // Partitioning with one pivot
+/*
+* Use the third of the five sorted elements as pivot.
+* This value is inexpensive approximation of the median.
+*/
+int pivot = a[e3];
 /*
 * Partitioning degenerates to the traditional 3-way
 * (or "Dutch National Flag") schema:
 *
 *   left part    center part              right part
 *   all in (great, right) > pivot
 *
 * Pointer k is the first index of ?-part.
 */
 for (int k = less; k <= great; ++k) {
-if (a[k] == pivot1) {
+if (a[k] == pivot) {
 continue;
 }
 int ak = a[k];
-if (ak < pivot1) { // Move a[k] to left part
+if (ak < pivot) { // Move a[k] to left part
 a[k] = a[less];
 a[less] = ak;
-less++;
+++less;
-} else { // a[k] > pivot1 - Move a[k] to right part
+} else { // a[k] > pivot - Move a[k] to right part
-while (a[great] > pivot1) {
+while (a[great] > pivot) {
-great--;
+--great;
 }
-if (a[great] < pivot1) { // a[great] <= pivot1
+if (a[great] < pivot) { // a[great] <= pivot
 a[k] = a[less];
 a[less] = a[great];
-less++;
+++less;
-} else { // a[great] == pivot1
+} else { // a[great] == pivot
 /*
-* Even though a[great] equals to pivot1, the
+* Even though a[great] equals to pivot, the
-* assignment a[k] = pivot1 may be incorrect,
+* assignment a[k] = pivot may be incorrect,
-* if a[great] and pivot1 are floating-point
+* if a[great] and pivot are floating-point
 * zeros of different signs. Therefore in float
 * and double sorting methods we have to use
 * more accurate assignment a[k] = a[great].
 */
-a[k] = pivot1;
+a[k] = pivot;
 }
 a[great] = ak;
-great--;
+--great;
 }
 }
 /*
 * Sort left and right parts recursively.
 * Sorts the specified array.
 *
 * @param a the array to be sorted
 */
 public static void sort(long[] a) {
-sort(a, 0, a.length - 1, true);
+sort(a, 0, a.length - 1);
 }
 /**
 * Sorts the specified range of the array.
 *
 * @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
 */
 public static void sort(long[] a, int left, int right) {
-sort(a, left, right, true);
+// Use Quicksort on small arrays
+if (right - left < QUICKSORT_THRESHOLD) {
+sort(a, left, right, true);
+return;
+}
+/*
+* Index run[i] is the start of i-th run
+* (ascending or descending sequence).
+*/
+int[] run = new int[MAX_RUN_COUNT];
+int count = 0; run[0] = left;
+// Check if the array is nearly sorted
+for (int k = left; k < right; run[count] = k) {
+if (a[k] < a[k + 1]) { // ascending
+while (++k <= right && a[k - 1] <= a[k]);
+} else if (a[k] > a[k + 1]) { // descending
+while (++k <= right && a[k - 1] >= a[k]);
+for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
+long t = a[lo]; a[lo] = a[hi]; a[hi] = t;
+}
+} else { // equal
+for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
+if (--m == 0) {
+sort(a, left, right, true);
+return;
+}
+}
+}
+/*
+* The array is not highly structured,
+* use Quicksort instead of merge sort.
+*/
+if (++count == MAX_RUN_COUNT) {
+sort(a, left, right, true);
+return;
+}
+}
+// Check special cases
+if (run[count] == right++) { // The last run contains one element
+run[++count] = right;
+} else if (count == 1) { // The array is already sorted
+return;
+}
+/*
+* Create temporary array, which is used for merging.
+* Implementation note: variable "right" is increased by 1.
+*/
+long[] b; byte odd = 0;
+for (int n = 1; (n <<= 1) < count; odd ^= 1);
+if (odd == 0) {
+b = a; a = new long[b.length];
+for (int i = left - 1; ++i < right; a[i] = b[i]);
+} else {
+b = new long[a.length];
+}
+// Merging
+for (int last; count > 1; count = last) {
+for (int k = (last = 0) + 2; k <= count; k += 2) {
+int hi = run[k], mi = run[k - 1];
+for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
+if (q >= hi || p < mi && a[p] <= a[q]) {
+b[i] = a[p++];
+} else {
+b[i] = a[q++];
+}
+}
+run[++last] = hi;
+}
+if ((count & 1) != 0) {
+for (int i = right, lo = run[count - 1]; --i >= lo;
+b[i] = a[i]
+);
+run[++last] = right;
+}
+long[] t = a; a = b; b = t;
+}
 }
 /**
 * Sorts the specified range of the array by Dual-Pivot Quicksort.
 *
 * @param leftmost indicates if this part is the leftmost in the range
 */
 private static void sort(long[] a, int left, int right, boolean leftmost) {
 int length = right - left + 1;
-// Use insertion sort on small arrays
+// Use insertion sort on tiny arrays
 if (length < INSERTION_SORT_THRESHOLD) {
 if (leftmost) {
 /*
 * Traditional (without sentinel) insertion sort,
 * optimized for server VM, is used in case of
 } else {
 /*
 * Skip the longest ascending sequence.
 */
 do {
-if (left++ >= right) {
+if (left >= right) {
 return;
 }
-} while (a[left - 1] <= a[left]);
+} while (a[++left] >= a[left - 1]);
 /*
 * Every element from adjoining part plays the role
 * of sentinel, therefore this allows us to avoid the
 * left range check on each iteration. Moreover, we use
-* the best improved algorithm, so called pair insertion
+* the more optimized algorithm, so called pair insertion
-* sort, which is faster than traditional implementation
+* sort, which is faster (in the context of Quicksort)
-* in the context of Dual-Pivot Quicksort.
+* than traditional implementation of insertion sort.
 */
-for (int k = left--; (left += 2) <= right; ) {
+for (int k = left; ++left <= right; k = ++left) {
-long a1, a2; k = left - 1;
+long a1 = a[k], a2 = a[left];
-if (a[k] < a[left]) {
+if (a1 < a2) {
-a2 = a[k]; a1 = a[left];
+a2 = a1; a1 = a[left];
-} else {
-a1 = a[k]; a2 = a[left];
 }
 while (a1 < a[--k]) {
 a[k + 2] = a[k];
 }
 a[++k + 1] = a1;
 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 }
 }
 }
-/*
-* Use the second and fourth of the five sorted elements as pivots.
-* These values are inexpensive approximations of the first and
-* second terciles of the array. Note that pivot1 <= pivot2.
-*/
-long pivot1 = a[e2];
-long pivot2 = a[e4];
 // Pointers
 int less  = left;  // The index of the first element of center part
 int great = right; // The index before the first element of right part
-if (pivot1 != pivot2) {
+if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
+/*
+* 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.
+*/
+long pivot1 = a[e2];
+long pivot2 = a[e4];
 /*
 * The first and the last elements to be sorted are moved to the
 * locations formerly occupied by the pivots. When partitioning
 * is complete, the pivots are swapped back into their final
 * positions, and excluded from subsequent sorting.
 /*
 * Here and below we use "a[i] = b; i++;" instead
 * of "a[i++] = b;" due to performance issue.
 */
 a[less] = ak;
-less++;
+++less;
 } else if (ak > pivot2) { // Move a[k] to right part
 while (a[great] > pivot2) {
 if (great-- == k) {
 break outer;
 }
 }
 if (a[great] < pivot1) { // a[great] <= pivot2
 a[k] = a[less];
 a[less] = a[great];
-less++;
+++less;
 } else { // pivot1 <= a[great] <= pivot2
 a[k] = a[great];
 }
 /*
 * Here and below we use "a[i] = b; i--;" instead
 * of "a[i--] = b;" due to performance issue.
 */
 a[great] = ak;
-great--;
+--great;
 }
 }
 // Swap pivots into their final positions
 a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
 if (less < e1 && e5 < great) {
 /*
 * Skip elements, which are equal to pivot values.
 */
 while (a[less] == pivot1) {
-less++;
+++less;
 }
 while (a[great] == pivot2) {
-great--;
+--great;
 }
 /*
 * Partitioning:
 *
 for (int k = less - 1; ++k <= great; ) {
 long ak = a[k];
 if (ak == pivot1) { // Move a[k] to left part
 a[k] = a[less];
 a[less] = ak;
-less++;
+++less;
 } else if (ak == pivot2) { // Move a[k] to right part
 while (a[great] == pivot2) {
 if (great-- == k) {
 break outer;
 }
 * of different signs. Therefore in float and
 * double sorting methods we have to use more
 * accurate assignment a[less] = a[great].
 */
 a[less] = pivot1;
-less++;
+++less;
 } else { // pivot1 < a[great] < pivot2
 a[k] = a[great];
 }
 a[great] = ak;
-great--;
+--great;
 }
 }
 }
 // Sort center part recursively
 sort(a, less, great, false);
-} else { // Pivots are equal
+} else { // Partitioning with one pivot
+/*
+* Use the third of the five sorted elements as pivot.
+* This value is inexpensive approximation of the median.
+*/
+long pivot = a[e3];
 /*
 * Partitioning degenerates to the traditional 3-way
 * (or "Dutch National Flag") schema:
 *
 *   left part    center part              right part
 *   all in (great, right) > pivot
 *
 * Pointer k is the first index of ?-part.
 */
 for (int k = less; k <= great; ++k) {
-if (a[k] == pivot1) {
+if (a[k] == pivot) {
 continue;
 }
 long ak = a[k];
-if (ak < pivot1) { // Move a[k] to left part
+if (ak < pivot) { // Move a[k] to left part
 a[k] = a[less];
 a[less] = ak;
-less++;
+++less;
-} else { // a[k] > pivot1 - Move a[k] to right part
+} else { // a[k] > pivot - Move a[k] to right part
-while (a[great] > pivot1) {
+while (a[great] > pivot) {
-great--;
+--great;
 }
-if (a[great] < pivot1) { // a[great] <= pivot1
+if (a[great] < pivot) { // a[great] <= pivot
 a[k] = a[less];
 a[less] = a[great];
-less++;
+++less;
-} else { // a[great] == pivot1
+} else { // a[great] == pivot
 /*
-* Even though a[great] equals to pivot1, the
+* Even though a[great] equals to pivot, the
-* assignment a[k] = pivot1 may be incorrect,
+* assignment a[k] = pivot may be incorrect,
-* if a[great] and pivot1 are floating-point
+* if a[great] and pivot are floating-point
 * zeros of different signs. Therefore in float
 * and double sorting methods we have to use
 * more accurate assignment a[k] = a[great].
 */
-a[k] = pivot1;
+a[k] = pivot;
 }
 a[great] = ak;
-great--;
+--great;
 }
 }
 /*
 * Sort left and right parts recursively.
 public static void sort(short[] a, int left, int right) {
 // Use counting sort on large arrays
 if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
 int[] count = new int[NUM_SHORT_VALUES];
-for (int i = left - 1; ++i <= right; ) {
+for (int i = left - 1; ++i <= right;
-count[a[i] - Short.MIN_VALUE]++;
+count[a[i] - Short.MIN_VALUE]++
-}
+);
 for (int i = NUM_SHORT_VALUES, k = right + 1; k > left; ) {
 while (count[--i] == 0);
 short value = (short) (i + Short.MIN_VALUE);
 int s = count[i];
 do {
 a[--k] = value;
 } while (--s > 0);
 }
 } else { // Use Dual-Pivot Quicksort on small arrays
-sort(a, left, right, true);
+doSort(a, left, right);
 }
 }
 /** The number of distinct short values. */
 private static final int NUM_SHORT_VALUES = 1 << 16;
+/**
+* Sorts the specified range of the array.
+*
+* @param a the array to be sorted
+* @param left the index of the first element, inclusive, to be sorted
+* @param right the index of the last element, inclusive, to be sorted
+*/
+private static void doSort(short[] a, int left, int right) {
+// Use Quicksort on small arrays
+if (right - left < QUICKSORT_THRESHOLD) {
+sort(a, left, right, true);
+return;
+}
+/*
+* Index run[i] is the start of i-th run
+* (ascending or descending sequence).
+*/
+int[] run = new int[MAX_RUN_COUNT];
+int count = 0; run[0] = left;
+// Check if the array is nearly sorted
+for (int k = left; k < right; run[count] = k) {
+if (a[k] < a[k + 1]) { // ascending
+while (++k <= right && a[k - 1] <= a[k]);
+} else if (a[k] > a[k + 1]) { // descending
+while (++k <= right && a[k - 1] >= a[k]);
+for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
+short t = a[lo]; a[lo] = a[hi]; a[hi] = t;
+}
+} else { // equal
+for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
+if (--m == 0) {
+sort(a, left, right, true);
+return;
+}
+}
+}
+/*
+* The array is not highly structured,
+* use Quicksort instead of merge sort.
+*/
+if (++count == MAX_RUN_COUNT) {
+sort(a, left, right, true);
+return;
+}
+}
+// Check special cases
+if (run[count] == right++) { // The last run contains one element
+run[++count] = right;
+} else if (count == 1) { // The array is already sorted
+return;
+}
+/*
+* Create temporary array, which is used for merging.
+* Implementation note: variable "right" is increased by 1.
+*/
+short[] b; byte odd = 0;
+for (int n = 1; (n <<= 1) < count; odd ^= 1);
+if (odd == 0) {
+b = a; a = new short[b.length];
+for (int i = left - 1; ++i < right; a[i] = b[i]);
+} else {
+b = new short[a.length];
+}
+// Merging
+for (int last; count > 1; count = last) {
+for (int k = (last = 0) + 2; k <= count; k += 2) {
+int hi = run[k], mi = run[k - 1];
+for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
+if (q >= hi || p < mi && a[p] <= a[q]) {
+b[i] = a[p++];
+} else {
+b[i] = a[q++];
+}
+}
+run[++last] = hi;
+}
+if ((count & 1) != 0) {
+for (int i = right, lo = run[count - 1]; --i >= lo;
+b[i] = a[i]
+);
+run[++last] = right;
+}
+short[] t = a; a = b; b = t;
+}
+}
 /**
 * Sorts the specified range of the array by Dual-Pivot Quicksort.
 *
 * @param a the array to be sorted
 * @param left the index of the first element, inclusive, to be sorted
 * @param right the index of the last element, inclusive, to be sorted
 * @param leftmost indicates if this part is the leftmost in the range
 */
-private static void sort(short[] a, int left, int right,boolean leftmost) {
+private static void sort(short[] a, int left, int right, boolean leftmost) {
 int length = right - left + 1;
-// Use insertion sort on small arrays
+// Use insertion sort on tiny arrays
 if (length < INSERTION_SORT_THRESHOLD) {
 if (leftmost) {
 /*
 * Traditional (without sentinel) insertion sort,
 * optimized for server VM, is used in case of
 } else {
 /*
 * Skip the longest ascending sequence.
 */
 do {
-if (left++ >= right) {
+if (left >= right) {
 return;
 }
-} while (a[left - 1] <= a[left]);
+} while (a[++left] >= a[left - 1]);
 /*
 * Every element from adjoining part plays the role
 * of sentinel, therefore this allows us to avoid the
 * left range check on each iteration. Moreover, we use
-* the best improved algorithm, so called pair insertion
+* the more optimized algorithm, so called pair insertion
-* sort, which is faster than traditional implementation
+* sort, which is faster (in the context of Quicksort)
-* in the context of Dual-Pivot Quicksort.
+* than traditional implementation of insertion sort.
 */
-for (int k = left--; (left += 2) <= right; ) {
+for (int k = left; ++left <= right; k = ++left) {
-short a1, a2; k = left - 1;
+short a1 = a[k], a2 = a[left];
-if (a[k] < a[left]) {
+if (a1 < a2) {
-a2 = a[k]; a1 = a[left];
+a2 = a1; a1 = a[left];
-} else {
-a1 = a[k]; a2 = a[left];
 }
 while (a1 < a[--k]) {
 a[k + 2] = a[k];
 }
 a[++k + 1] = a1;
 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 }
 }
 }
-/*
-* Use the second and fourth of the five sorted elements as pivots.
-* These values are inexpensive approximations of the first and
-* second terciles of the array. Note that pivot1 <= pivot2.
-*/
-short pivot1 = a[e2];
-short pivot2 = a[e4];
 // Pointers
 int less  = left;  // The index of the first element of center part
 int great = right; // The index before the first element of right part
-if (pivot1 != pivot2) {
+if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
+/*
+* 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.
+*/
+short pivot1 = a[e2];
+short pivot2 = a[e4];
 /*
 * The first and the last elements to be sorted are moved to the
 * locations formerly occupied by the pivots. When partitioning
 * is complete, the pivots are swapped back into their final
 * positions, and excluded from subsequent sorting.
 /*
 * Here and below we use "a[i] = b; i++;" instead
 * of "a[i++] = b;" due to performance issue.
 */
 a[less] = ak;
-less++;
+++less;
 } else if (ak > pivot2) { // Move a[k] to right part
 while (a[great] > pivot2) {
 if (great-- == k) {
 break outer;
 }
 }
 if (a[great] < pivot1) { // a[great] <= pivot2
 a[k] = a[less];
 a[less] = a[great];
-less++;
+++less;
 } else { // pivot1 <= a[great] <= pivot2
 a[k] = a[great];
 }
 /*
 * Here and below we use "a[i] = b; i--;" instead
 * of "a[i--] = b;" due to performance issue.
 */
 a[great] = ak;
-great--;
+--great;
 }
 }
 // Swap pivots into their final positions
 a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
 if (less < e1 && e5 < great) {
 /*
 * Skip elements, which are equal to pivot values.
 */
 while (a[less] == pivot1) {
-less++;
+++less;
 }
 while (a[great] == pivot2) {
-great--;
+--great;
 }
 /*
 * Partitioning:
 *
 for (int k = less - 1; ++k <= great; ) {
 short ak = a[k];
 if (ak == pivot1) { // Move a[k] to left part
 a[k] = a[less];
 a[less] = ak;
-less++;
+++less;
 } else if (ak == pivot2) { // Move a[k] to right part
 while (a[great] == pivot2) {
 if (great-- == k) {
 break outer;
 }
 * of different signs. Therefore in float and
 * double sorting methods we have to use more
 * accurate assignment a[less] = a[great].
 */
 a[less] = pivot1;
-less++;
+++less;
 } else { // pivot1 < a[great] < pivot2
 a[k] = a[great];
 }
 a[great] = ak;
-great--;
+--great;
 }
 }
 }
 // Sort center part recursively
 sort(a, less, great, false);
-} else { // Pivots are equal
+} else { // Partitioning with one pivot
+/*
+* Use the third of the five sorted elements as pivot.
+* This value is inexpensive approximation of the median.
+*/
+short pivot = a[e3];
 /*
 * Partitioning degenerates to the traditional 3-way
 * (or "Dutch National Flag") schema:
 *
 *   left part    center part              right part
 *   all in (great, right) > pivot
 *
 * Pointer k is the first index of ?-part.
 */
 for (int k = less; k <= great; ++k) {
-if (a[k] == pivot1) {
+if (a[k] == pivot) {
 continue;
 }
 short ak = a[k];
-if (ak < pivot1) { // Move a[k] to left part
+if (ak < pivot) { // Move a[k] to left part
 a[k] = a[less];
 a[less] = ak;
-less++;
+++less;
-} else { // a[k] > pivot1 - Move a[k] to right part
+} else { // a[k] > pivot - Move a[k] to right part
-while (a[great] > pivot1) {
+while (a[great] > pivot) {
-great--;
+--great;
 }
-if (a[great] < pivot1) { // a[great] <= pivot1
+if (a[great] < pivot) { // a[great] <= pivot
 a[k] = a[less];
 a[less] = a[great];
-less++;
+++less;
-} else { // a[great] == pivot1
+} else { // a[great] == pivot
 /*
-* Even though a[great] equals to pivot1, the
+* Even though a[great] equals to pivot, the
-* assignment a[k] = pivot1 may be incorrect,
+* assignment a[k] = pivot may be incorrect,
-* if a[great] and pivot1 are floating-point
+* if a[great] and pivot are floating-point
 * zeros of different signs. Therefore in float
 * and double sorting methods we have to use
 * more accurate assignment a[k] = a[great].
 */
-a[k] = pivot1;
+a[k] = pivot;
 }
 a[great] = ak;
-great--;
+--great;
 }
 }
 /*
 * Sort left and right parts recursively.
 public static void sort(char[] a, int left, int right) {
 // Use counting sort on large arrays
 if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
 int[] count = new int[NUM_CHAR_VALUES];
-for (int i = left - 1; ++i <= right; ) {
+for (int i = left - 1; ++i <= right;
-count[a[i]]++;
+count[a[i]]++
-}
+);
 for (int i = NUM_CHAR_VALUES, k = right + 1; k > left; ) {
 while (count[--i] == 0);
 char value = (char) i;
 int s = count[i];
 do {
 a[--k] = value;
 } while (--s > 0);
 }
 } else { // Use Dual-Pivot Quicksort on small arrays
-sort(a, left, right, true);
+doSort(a, left, right);
 }
 }
 /** The number of distinct char values. */
 private static final int NUM_CHAR_VALUES = 1 << 16;
+/**
+* Sorts the specified range of the array.
+*
+* @param a the array to be sorted
+* @param left the index of the first element, inclusive, to be sorted
+* @param right the index of the last element, inclusive, to be sorted
+*/
+private static void doSort(char[] a, int left, int right) {
+// Use Quicksort on small arrays
+if (right - left < QUICKSORT_THRESHOLD) {
+sort(a, left, right, true);
+return;
+}
+/*
+* Index run[i] is the start of i-th run
+* (ascending or descending sequence).
+*/
+int[] run = new int[MAX_RUN_COUNT];
+int count = 0; run[0] = left;
+// Check if the array is nearly sorted
+for (int k = left; k < right; run[count] = k) {
+if (a[k] < a[k + 1]) { // ascending
+while (++k <= right && a[k - 1] <= a[k]);
+} else if (a[k] > a[k + 1]) { // descending
+while (++k <= right && a[k - 1] >= a[k]);
+for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
+char t = a[lo]; a[lo] = a[hi]; a[hi] = t;
+}
+} else { // equal
+for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
+if (--m == 0) {
+sort(a, left, right, true);
+return;
+}
+}
+}
+/*
+* The array is not highly structured,
+* use Quicksort instead of merge sort.
+*/
+if (++count == MAX_RUN_COUNT) {
+sort(a, left, right, true);
+return;
+}
+}
+// Check special cases
+if (run[count] == right++) { // The last run contains one element
+run[++count] = right;
+} else if (count == 1) { // The array is already sorted
+return;
+}
+/*
+* Create temporary array, which is used for merging.
+* Implementation note: variable "right" is increased by 1.
+*/
+char[] b; byte odd = 0;
+for (int n = 1; (n <<= 1) < count; odd ^= 1);
+if (odd == 0) {
+b = a; a = new char[b.length];
+for (int i = left - 1; ++i < right; a[i] = b[i]);
+} else {
+b = new char[a.length];
+}
+// Merging
+for (int last; count > 1; count = last) {
+for (int k = (last = 0) + 2; k <= count; k += 2) {
+int hi = run[k], mi = run[k - 1];
+for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
+if (q >= hi || p < mi && a[p] <= a[q]) {
+b[i] = a[p++];
+} else {
+b[i] = a[q++];
+}
+}
+run[++last] = hi;
+}
+if ((count & 1) != 0) {
+for (int i = right, lo = run[count - 1]; --i >= lo;
+b[i] = a[i]
+);
+run[++last] = right;
+}
+char[] t = a; a = b; b = t;
+}
+}
 /**
 * Sorts the specified range of the array by Dual-Pivot Quicksort.
 *
 * @param a the array to be sorted
 * @param leftmost indicates if this part is the leftmost in the range
 */
 private static void sort(char[] a, int left, int right, boolean leftmost) {
 int length = right - left + 1;
-// Use insertion sort on small arrays
+// Use insertion sort on tiny arrays
 if (length < INSERTION_SORT_THRESHOLD) {
 if (leftmost) {
 /*
 * Traditional (without sentinel) insertion sort,
 * optimized for server VM, is used in case of
 } else {
 /*
 * Skip the longest ascending sequence.
 */
 do {
-if (left++ >= right) {
+if (left >= right) {
 return;
 }
-} while (a[left - 1] <= a[left]);
+} while (a[++left] >= a[left - 1]);
 /*
 * Every element from adjoining part plays the role
 * of sentinel, therefore this allows us to avoid the
 * left range check on each iteration. Moreover, we use
-* the best improved algorithm, so called pair insertion
+* the more optimized algorithm, so called pair insertion
-* sort, which is faster than traditional implementation
+* sort, which is faster (in the context of Quicksort)
-* in the context of Dual-Pivot Quicksort.
+* than traditional implementation of insertion sort.
 */
-for (int k = left--; (left += 2) <= right; ) {
+for (int k = left; ++left <= right; k = ++left) {
-char a1, a2; k = left - 1;
+char a1 = a[k], a2 = a[left];
-if (a[k] < a[left]) {
+if (a1 < a2) {
-a2 = a[k]; a1 = a[left];
+a2 = a1; a1 = a[left];
-} else {
-a1 = a[k]; a2 = a[left];
 }
 while (a1 < a[--k]) {
 a[k + 2] = a[k];
 }
 a[++k + 1] = a1;
 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 }
 }
 }
-/*
-* Use the second and fourth of the five sorted elements as pivots.
-* These values are inexpensive approximations of the first and
-* second terciles of the array. Note that pivot1 <= pivot2.
-*/
-char pivot1 = a[e2];
-char pivot2 = a[e4];
 // Pointers
 int less  = left;  // The index of the first element of center part
 int great = right; // The index before the first element of right part
-if (pivot1 != pivot2) {
+if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
+/*
+* 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.
+*/
+char pivot1 = a[e2];
+char pivot2 = a[e4];
 /*
 * The first and the last elements to be sorted are moved to the
 * locations formerly occupied by the pivots. When partitioning
 * is complete, the pivots are swapped back into their final
 * positions, and excluded from subsequent sorting.
 /*
 * Here and below we use "a[i] = b; i++;" instead
 * of "a[i++] = b;" due to performance issue.
 */
 a[less] = ak;
-less++;
+++less;
 } else if (ak > pivot2) { // Move a[k] to right part
 while (a[great] > pivot2) {
 if (great-- == k) {
 break outer;
 }
 }
 if (a[great] < pivot1) { // a[great] <= pivot2
 a[k] = a[less];
 a[less] = a[great];
-less++;
+++less;
 } else { // pivot1 <= a[great] <= pivot2
 a[k] = a[great];
 }
 /*
 * Here and below we use "a[i] = b; i--;" instead
 * of "a[i--] = b;" due to performance issue.
 */
 a[great] = ak;
-great--;
+--great;
 }
 }
 // Swap pivots into their final positions
 a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
 if (less < e1 && e5 < great) {
 /*
 * Skip elements, which are equal to pivot values.
 */
 while (a[less] == pivot1) {
-less++;
+++less;
 }
 while (a[great] == pivot2) {
-great--;
+--great;
 }
 /*
 * Partitioning:
 *
 for (int k = less - 1; ++k <= great; ) {
 char ak = a[k];
 if (ak == pivot1) { // Move a[k] to left part
 a[k] = a[less];
 a[less] = ak;
-less++;
+++less;
 } else if (ak == pivot2) { // Move a[k] to right part
 while (a[great] == pivot2) {
 if (great-- == k) {
 break outer;
 }
 * of different signs. Therefore in float and
 * double sorting methods we have to use more
 * accurate assignment a[less] = a[great].
 */
 a[less] = pivot1;
-less++;
+++less;
 } else { // pivot1 < a[great] < pivot2
 a[k] = a[great];
 }
 a[great] = ak;
-great--;
+--great;
 }
 }
 }
 // Sort center part recursively
 sort(a, less, great, false);
-} else { // Pivots are equal
+} else { // Partitioning with one pivot
+/*
+* Use the third of the five sorted elements as pivot.
+* This value is inexpensive approximation of the median.
+*/
+char pivot = a[e3];
 /*
 * Partitioning degenerates to the traditional 3-way
 * (or "Dutch National Flag") schema:
 *
 *   left part    center part              right part
 *   all in (great, right) > pivot
 *
 * Pointer k is the first index of ?-part.
 */
 for (int k = less; k <= great; ++k) {
-if (a[k] == pivot1) {
+if (a[k] == pivot) {
 continue;
 }
 char ak = a[k];
-if (ak < pivot1) { // Move a[k] to left part
+if (ak < pivot) { // Move a[k] to left part
 a[k] = a[less];
 a[less] = ak;
-less++;
+++less;
-} else { // a[k] > pivot1 - Move a[k] to right part
+} else { // a[k] > pivot - Move a[k] to right part
-while (a[great] > pivot1) {
+while (a[great] > pivot) {
-great--;
+--great;
 }
-if (a[great] < pivot1) { // a[great] <= pivot1
+if (a[great] < pivot) { // a[great] <= pivot
 a[k] = a[less];
 a[less] = a[great];
-less++;
+++less;
-} else { // a[great] == pivot1
+} else { // a[great] == pivot
 /*
-* Even though a[great] equals to pivot1, the
+* Even though a[great] equals to pivot, the
-* assignment a[k] = pivot1 may be incorrect,
+* assignment a[k] = pivot may be incorrect,
-* if a[great] and pivot1 are floating-point
+* if a[great] and pivot are floating-point
 * zeros of different signs. Therefore in float
 * and double sorting methods we have to use
 * more accurate assignment a[k] = a[great].
 */
-a[k] = pivot1;
+a[k] = pivot;
 }
 a[great] = ak;
-great--;
+--great;
 }
 }
 /*
 * Sort left and right parts recursively.
 public static void sort(byte[] a, int left, int right) {
 // Use counting sort on large arrays
 if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
 int[] count = new int[NUM_BYTE_VALUES];
-for (int i = left - 1; ++i <= right; ) {
+for (int i = left - 1; ++i <= right;
-count[a[i] - Byte.MIN_VALUE]++;
+count[a[i] - Byte.MIN_VALUE]++
-}
+);
 for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) {
 while (count[--i] == 0);
 byte value = (byte) (i + Byte.MIN_VALUE);
 int s = count[i];
 public static void sort(float[] a, int left, int right) {
 /*
 * Phase 1: Move NaNs to the end of the array.
 */
 while (left <= right && Float.isNaN(a[right])) {
-right--;
+--right;
 }
 for (int k = right; --k >= left; ) {
 float ak = a[k];
 if (ak != ak) { // a[k] is NaN
 a[k] = a[right];
 a[right] = ak;
-right--;
+--right;
 }
 }
 /*
 * Phase 2: Sort everything except NaNs (which are already in place).
 */
-sort(a, left, right, true);
+doSort(a, left, right);
 /*
 * Phase 3: Place negative zeros before positive zeros.
 */
 int hi = right;
 /*
 * Skip the last negative value (if any) or all leading negative zeros.
 */
 while (left <= right && Float.floatToRawIntBits(a[left]) < 0) {
-left++;
+++left;
 }
 /*
 * Move negative zeros to the beginning of the sub-range.
 *
 }
 }
 }
 /**
+* Sorts the specified range of the array.
+*
+* @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(float[] a, int left, int right) {
+// Use Quicksort on small arrays
+if (right - left < QUICKSORT_THRESHOLD) {
+sort(a, left, right, true);
+return;
+}
+/*
+* Index run[i] is the start of i-th run
+* (ascending or descending sequence).
+*/
+int[] run = new int[MAX_RUN_COUNT];
+int count = 0; run[0] = left;
+// Check if the array is nearly sorted
+for (int k = left; k < right; run[count] = k) {
+if (a[k] < a[k + 1]) { // ascending
+while (++k <= right && a[k - 1] <= a[k]);
+} else if (a[k] > a[k + 1]) { // descending
+while (++k <= right && a[k - 1] >= a[k]);
+for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
+float t = a[lo]; a[lo] = a[hi]; a[hi] = t;
+}
+} else { // equal
+for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
+if (--m == 0) {
+sort(a, left, right, true);
+return;
+}
+}
+}
+/*
+* The array is not highly structured,
+* use Quicksort instead of merge sort.
+*/
+if (++count == MAX_RUN_COUNT) {
+sort(a, left, right, true);
+return;
+}
+}
+// Check special cases
+if (run[count] == right++) { // The last run contains one element
+run[++count] = right;
+} else if (count == 1) { // The array is already sorted
+return;
+}
+/*
+* Create temporary array, which is used for merging.
+* Implementation note: variable "right" is increased by 1.
+*/
+float[] b; byte odd = 0;
+for (int n = 1; (n <<= 1) < count; odd ^= 1);
+if (odd == 0) {
+b = a; a = new float[b.length];
+for (int i = left - 1; ++i < right; a[i] = b[i]);
+} else {
+b = new float[a.length];
+}
+// Merging
+for (int last; count > 1; count = last) {
+for (int k = (last = 0) + 2; k <= count; k += 2) {
+int hi = run[k], mi = run[k - 1];
+for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
+if (q >= hi || p < mi && a[p] <= a[q]) {
+b[i] = a[p++];
+} else {
+b[i] = a[q++];
+}
+}
+run[++last] = hi;
+}
+if ((count & 1) != 0) {
+for (int i = right, lo = run[count - 1]; --i >= lo;
+b[i] = a[i]
+);
+run[++last] = right;
+}
+float[] t = a; a = b; b = t;
+}
+}
+/**
 * Sorts the specified range of the array by Dual-Pivot Quicksort.
 *
 * @param a the array to be sorted
 * @param left the index of the first element, inclusive, to be sorted
 * @param right the index of the last element, inclusive, to be sorted
 * @param leftmost indicates if this part is the leftmost in the range
 */
-private static void sort(float[] a, int left, int right,boolean leftmost) {
+private static void sort(float[] a, int left, int right, boolean leftmost) {
 int length = right - left + 1;
-// Use insertion sort on small arrays
+// Use insertion sort on tiny arrays
 if (length < INSERTION_SORT_THRESHOLD) {
 if (leftmost) {
 /*
 * Traditional (without sentinel) insertion sort,
 * optimized for server VM, is used in case of
 } else {
 /*
 * Skip the longest ascending sequence.
 */
 do {
-if (left++ >= right) {
+if (left >= right) {
 return;
 }
-} while (a[left - 1] <= a[left]);
+} while (a[++left] >= a[left - 1]);
 /*
 * Every element from adjoining part plays the role
 * of sentinel, therefore this allows us to avoid the
 * left range check on each iteration. Moreover, we use
-* the best improved algorithm, so called pair insertion
+* the more optimized algorithm, so called pair insertion
-* sort, which is faster than traditional implementation
+* sort, which is faster (in the context of Quicksort)
-* in the context of Dual-Pivot Quicksort.
+* than traditional implementation of insertion sort.
 */
-for (int k = left--; (left += 2) <= right; ) {
+for (int k = left; ++left <= right; k = ++left) {
-float a1, a2; k = left - 1;
+float a1 = a[k], a2 = a[left];
-if (a[k] < a[left]) {
+if (a1 < a2) {
-a2 = a[k]; a1 = a[left];
+a2 = a1; a1 = a[left];
-} else {
-a1 = a[k]; a2 = a[left];
 }
 while (a1 < a[--k]) {
 a[k + 2] = a[k];
 }
 a[++k + 1] = a1;
 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 }
 }
 }
-/*
-* Use the second and fourth of the five sorted elements as pivots.
-* These values are inexpensive approximations of the first and
-* second terciles of the array. Note that pivot1 <= pivot2.
-*/
-float pivot1 = a[e2];
-float pivot2 = a[e4];
 // Pointers
 int less  = left;  // The index of the first element of center part
 int great = right; // The index before the first element of right part
-if (pivot1 != pivot2) {
+if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
+/*
+* 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.
+*/
+float pivot1 = a[e2];
+float pivot2 = a[e4];
 /*
 * The first and the last elements to be sorted are moved to the
 * locations formerly occupied by the pivots. When partitioning
 * is complete, the pivots are swapped back into their final
 * positions, and excluded from subsequent sorting.
 /*
 * Here and below we use "a[i] = b; i++;" instead
 * of "a[i++] = b;" due to performance issue.
 */
 a[less] = ak;
-less++;
+++less;
 } else if (ak > pivot2) { // Move a[k] to right part
 while (a[great] > pivot2) {
 if (great-- == k) {
 break outer;
 }
 }
 if (a[great] < pivot1) { // a[great] <= pivot2
 a[k] = a[less];
 a[less] = a[great];
-less++;
+++less;
 } else { // pivot1 <= a[great] <= pivot2
 a[k] = a[great];
 }
 /*
 * Here and below we use "a[i] = b; i--;" instead
 * of "a[i--] = b;" due to performance issue.
 */
 a[great] = ak;
-great--;
+--great;
 }
 }
 // Swap pivots into their final positions
 a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
 if (less < e1 && e5 < great) {
 /*
 * Skip elements, which are equal to pivot values.
 */
 while (a[less] == pivot1) {
-less++;
+++less;
 }
 while (a[great] == pivot2) {
-great--;
+--great;
 }
 /*
 * Partitioning:
 *
 for (int k = less - 1; ++k <= great; ) {
 float ak = a[k];
 if (ak == pivot1) { // Move a[k] to left part
 a[k] = a[less];
 a[less] = ak;
-less++;
+++less;
 } else if (ak == pivot2) { // Move a[k] to right part
 while (a[great] == pivot2) {
 if (great-- == k) {
 break outer;
 }
 * of different signs. Therefore in float and
 * double sorting methods we have to use more
 * accurate assignment a[less] = a[great].
 */
 a[less] = a[great];
-less++;
+++less;
 } else { // pivot1 < a[great] < pivot2
 a[k] = a[great];
 }
 a[great] = ak;
-great--;
+--great;
 }
 }
 }
 // Sort center part recursively
 sort(a, less, great, false);
-} else { // Pivots are equal
+} else { // Partitioning with one pivot
+/*
+* Use the third of the five sorted elements as pivot.
+* This value is inexpensive approximation of the median.
+*/
+float pivot = a[e3];
 /*
 * Partitioning degenerates to the traditional 3-way
 * (or "Dutch National Flag") schema:
 *
 *   left part    center part              right part
 *   all in (great, right) > pivot
 *
 * Pointer k is the first index of ?-part.
 */
 for (int k = less; k <= great; ++k) {
-if (a[k] == pivot1) {
+if (a[k] == pivot) {
 continue;
 }
 float ak = a[k];
-if (ak < pivot1) { // Move a[k] to left part
+if (ak < pivot) { // Move a[k] to left part
 a[k] = a[less];
 a[less] = ak;
-less++;
+++less;
-} else { // a[k] > pivot1 - Move a[k] to right part
+} else { // a[k] > pivot - Move a[k] to right part
-while (a[great] > pivot1) {
+while (a[great] > pivot) {
-great--;
+--great;
 }
-if (a[great] < pivot1) { // a[great] <= pivot1
+if (a[great] < pivot) { // a[great] <= pivot
 a[k] = a[less];
 a[less] = a[great];
-less++;
+++less;
-} else { // a[great] == pivot1
+} else { // a[great] == pivot
 /*
-* Even though a[great] equals to pivot1, the
+* Even though a[great] equals to pivot, the
-* assignment a[k] = pivot1 may be incorrect,
+* assignment a[k] = pivot may be incorrect,
-* if a[great] and pivot1 are floating-point
+* if a[great] and pivot are floating-point
 * zeros of different signs. Therefore in float
 * and double sorting methods we have to use
 * more accurate assignment a[k] = a[great].
 */
 a[k] = a[great];
 }
 a[great] = ak;
-great--;
+--great;
 }
 }
 /*
 * Sort left and right parts recursively.
 public static void sort(double[] a, int left, int right) {
 /*
 * Phase 1: Move NaNs to the end of the array.
 */
 while (left <= right && Double.isNaN(a[right])) {
-right--;
+--right;
 }
 for (int k = right; --k >= left; ) {
 double ak = a[k];
 if (ak != ak) { // a[k] is NaN
 a[k] = a[right];
 a[right] = ak;
-right--;
+--right;
 }
 }
 /*
 * Phase 2: Sort everything except NaNs (which are already in place).
 */
-sort(a, left, right, true);
+doSort(a, left, right);
 /*
 * Phase 3: Place negative zeros before positive zeros.
 */
 int hi = right;
 /*
 * Skip the last negative value (if any) or all leading negative zeros.
 */
 while (left <= right && Double.doubleToRawLongBits(a[left]) < 0) {
-left++;
+++left;
 }
 /*
 * Move negative zeros to the beginning of the sub-range.
 *
 }
 }
 }
 /**
+* Sorts the specified range of the array.
+*
+* @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(double[] a, int left, int right) {
+// Use Quicksort on small arrays
+if (right - left < QUICKSORT_THRESHOLD) {
+sort(a, left, right, true);
+return;
+}
+/*
+* Index run[i] is the start of i-th run
+* (ascending or descending sequence).
+*/
+int[] run = new int[MAX_RUN_COUNT];
+int count = 0; run[0] = left;
+// Check if the array is nearly sorted
+for (int k = left; k < right; run[count] = k) {
+if (a[k] < a[k + 1]) { // ascending
+while (++k <= right && a[k - 1] <= a[k]);
+} else if (a[k] > a[k + 1]) { // descending
+while (++k <= right && a[k - 1] >= a[k]);
+for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
+double t = a[lo]; a[lo] = a[hi]; a[hi] = t;
+}
+} else { // equal
+for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
+if (--m == 0) {
+sort(a, left, right, true);
+return;
+}
+}
+}
+/*
+* The array is not highly structured,
+* use Quicksort instead of merge sort.
+*/
+if (++count == MAX_RUN_COUNT) {
+sort(a, left, right, true);
+return;
+}
+}
+// Check special cases
+if (run[count] == right++) { // The last run contains one element
+run[++count] = right;
+} else if (count == 1) { // The array is already sorted
+return;
+}
+/*
+* Create temporary array, which is used for merging.
+* Implementation note: variable "right" is increased by 1.
+*/
+double[] b; byte odd = 0;
+for (int n = 1; (n <<= 1) < count; odd ^= 1);
+if (odd == 0) {
+b = a; a = new double[b.length];
+for (int i = left - 1; ++i < right; a[i] = b[i]);
+} else {
+b = new double[a.length];
+}
+// Merging
+for (int last; count > 1; count = last) {
+for (int k = (last = 0) + 2; k <= count; k += 2) {
+int hi = run[k], mi = run[k - 1];
+for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
+if (q >= hi || p < mi && a[p] <= a[q]) {
+b[i] = a[p++];
+} else {
+b[i] = a[q++];
+}
+}
+run[++last] = hi;
+}
+if ((count & 1) != 0) {
+for (int i = right, lo = run[count - 1]; --i >= lo;
+b[i] = a[i]
+);
+run[++last] = right;
+}
+double[] t = a; a = b; b = t;
+}
+}
+/**
 * Sorts the specified range of the array by Dual-Pivot Quicksort.
 *
 * @param a the array to be sorted
 * @param left the index of the first element, inclusive, to be sorted
 * @param right the index of the last element, inclusive, to be sorted
 * @param leftmost indicates if this part is the leftmost in the range
 */
-private static void sort(double[] a, int left,int right,boolean leftmost) {
+private static void sort(double[] a, int left, int right, boolean leftmost) {
 int length = right - left + 1;
-// Use insertion sort on small arrays
+// Use insertion sort on tiny arrays
 if (length < INSERTION_SORT_THRESHOLD) {
 if (leftmost) {
 /*
 * Traditional (without sentinel) insertion sort,
 * optimized for server VM, is used in case of
 } else {
 /*
 * Skip the longest ascending sequence.
 */
 do {
-if (left++ >= right) {
+if (left >= right) {
 return;
 }
-} while (a[left - 1] <= a[left]);
+} while (a[++left] >= a[left - 1]);
 /*
 * Every element from adjoining part plays the role
 * of sentinel, therefore this allows us to avoid the
 * left range check on each iteration. Moreover, we use
-* the best improved algorithm, so called pair insertion
+* the more optimized algorithm, so called pair insertion
-* sort, which is faster than traditional implementation
+* sort, which is faster (in the context of Quicksort)
-* in the context of Dual-Pivot Quicksort.
+* than traditional implementation of insertion sort.
 */
-for (int k = left--; (left += 2) <= right; ) {
+for (int k = left; ++left <= right; k = ++left) {
-double a1, a2; k = left - 1;
+double a1 = a[k], a2 = a[left];
-if (a[k] < a[left]) {
+if (a1 < a2) {
-a2 = a[k]; a1 = a[left];
+a2 = a1; a1 = a[left];
-} else {
-a1 = a[k]; a2 = a[left];
 }
 while (a1 < a[--k]) {
 a[k + 2] = a[k];
 }
 a[++k + 1] = a1;
 if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
 }
 }
 }
-/*
-* Use the second and fourth of the five sorted elements as pivots.
-* These values are inexpensive approximations of the first and
-* second terciles of the array. Note that pivot1 <= pivot2.
-*/
-double pivot1 = a[e2];
-double pivot2 = a[e4];
 // Pointers
 int less  = left;  // The index of the first element of center part
 int great = right; // The index before the first element of right part
-if (pivot1 != pivot2) {
+if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
+/*
+* 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.
+*/
+double pivot1 = a[e2];
+double pivot2 = a[e4];
 /*
 * The first and the last elements to be sorted are moved to the
 * locations formerly occupied by the pivots. When partitioning
 * is complete, the pivots are swapped back into their final
 * positions, and excluded from subsequent sorting.
 /*
 * Here and below we use "a[i] = b; i++;" instead
 * of "a[i++] = b;" due to performance issue.
 */
 a[less] = ak;
-less++;
+++less;
 } else if (ak > pivot2) { // Move a[k] to right part
 while (a[great] > pivot2) {
 if (great-- == k) {
 break outer;
 }
 }
 if (a[great] < pivot1) { // a[great] <= pivot2
 a[k] = a[less];
 a[less] = a[great];
-less++;
+++less;
 } else { // pivot1 <= a[great] <= pivot2
 a[k] = a[great];
 }
 /*
 * Here and below we use "a[i] = b; i--;" instead
 * of "a[i--] = b;" due to performance issue.
 */
 a[great] = ak;
-great--;
+--great;
 }
 }
 // Swap pivots into their final positions
 a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
 if (less < e1 && e5 < great) {
 /*
 * Skip elements, which are equal to pivot values.
 */
 while (a[less] == pivot1) {
-less++;
+++less;
 }
 while (a[great] == pivot2) {
-great--;
+--great;
 }
 /*
 * Partitioning:
 *
 for (int k = less - 1; ++k <= great; ) {
 double ak = a[k];
 if (ak == pivot1) { // Move a[k] to left part
 a[k] = a[less];
 a[less] = ak;
-less++;
+++less;
 } else if (ak == pivot2) { // Move a[k] to right part
 while (a[great] == pivot2) {
 if (great-- == k) {
 break outer;
 }
 * of different signs. Therefore in float and
 * double sorting methods we have to use more
 * accurate assignment a[less] = a[great].
 */
 a[less] = a[great];
-less++;
+++less;
 } else { // pivot1 < a[great] < pivot2
 a[k] = a[great];
 }
 a[great] = ak;
-great--;
+--great;
 }
 }
 }
 // Sort center part recursively
 sort(a, less, great, false);
-} else { // Pivots are equal
+} else { // Partitioning with one pivot
+/*
+* Use the third of the five sorted elements as pivot.
+* This value is inexpensive approximation of the median.
+*/
+double pivot = a[e3];
 /*
 * Partitioning degenerates to the traditional 3-way
 * (or "Dutch National Flag") schema:
 *
 *   left part    center part              right part
 *   all in (great, right) > pivot
 *
 * Pointer k is the first index of ?-part.
 */
 for (int k = less; k <= great; ++k) {
-if (a[k] == pivot1) {
+if (a[k] == pivot) {
 continue;
 }
 double ak = a[k];
-if (ak < pivot1) { // Move a[k] to left part
+if (ak < pivot) { // Move a[k] to left part
 a[k] = a[less];
 a[less] = ak;
-less++;
+++less;
-} else { // a[k] > pivot1 - Move a[k] to right part
+} else { // a[k] > pivot - Move a[k] to right part
-while (a[great] > pivot1) {
+while (a[great] > pivot) {
-great--;
+--great;
 }
-if (a[great] < pivot1) { // a[great] <= pivot1
+if (a[great] < pivot) { // a[great] <= pivot
 a[k] = a[less];
 a[less] = a[great];
-less++;
+++less;
-} else { // a[great] == pivot1
+} else { // a[great] == pivot
 /*
-* Even though a[great] equals to pivot1, the
+* Even though a[great] equals to pivot, the
-* assignment a[k] = pivot1 may be incorrect,
+* assignment a[k] = pivot may be incorrect,
-* if a[great] and pivot1 are floating-point
+* if a[great] and pivot are floating-point
 * zeros of different signs. Therefore in float
 * and double sorting methods we have to use
 * more accurate assignment a[k] = a[great].
 */
 a[k] = a[great];
 }
 a[great] = ak;
-great--;
+--great;
 }
 }
 /*
 * Sort left and right parts recursively.

changeset 8188	b90884cf34f5
parent 6896	d229d56fd918
child 8193	626b859aabb2