# HG changeset patch
# User alanb
# Date 1297180230 0
# Node ID b90884cf34f57fe2218e1d6579b1c0a95637bb5f
# Parent cbd5448015d89b995f3410f855fb3e67b91bf856
7013585: Dual-pivot quicksort improvements for highly structured (nearly sorted) and data with small periods
Reviewed-by: mduigou, alanb
Contributed-by: vladimir.yaroslavskiy@oracle.com
diff -r cbd5448015d8 -r b90884cf34f5 jdk/src/share/classes/java/util/DualPivotQuicksort.java
--- a/jdk/src/share/classes/java/util/DualPivotQuicksort.java Mon Feb 07 18:02:30 2011 +0000
+++ b/jdk/src/share/classes/java/util/DualPivotQuicksort.java Tue Feb 08 15:50:30 2011 +0000
@@ -36,7 +36,7 @@
* @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 {
@@ -51,6 +51,22 @@
*/
/**
+ * 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.
*/
@@ -78,7 +94,7 @@
* @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);
}
/**
@@ -89,7 +105,89 @@
* @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;
+ }
}
/**
@@ -103,7 +201,7 @@
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) {
/*
@@ -126,26 +224,24 @@
* 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
- * sort, which is faster than traditional implementation
- * in the context of Dual-Pivot Quicksort.
+ * the more optimized algorithm, so called pair insertion
+ * sort, which is faster (in the context of Quicksort)
+ * than traditional implementation of insertion sort.
*/
- for (int k = left--; (left += 2) <= right; ) {
- int a1, a2; k = left - 1;
+ for (int k = left; ++left <= right; k = ++left) {
+ int a1 = a[k], a2 = a[left];
- if (a[k] < a[left]) {
- a2 = a[k]; a1 = a[left];
- } else {
- a1 = a[k]; a2 = a[left];
+ if (a1 < a2) {
+ a2 = a1; a1 = a[left];
}
while (a1 < a[--k]) {
a[k + 2] = a[k];
@@ -202,19 +298,19 @@
}
}
- /*
- * 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
@@ -259,7 +355,7 @@
* 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) {
@@ -269,7 +365,7 @@
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];
}
@@ -278,7 +374,7 @@
* of "a[i--] = b;" due to performance issue.
*/
a[great] = ak;
- great--;
+ --great;
}
}
@@ -299,10 +395,11 @@
* Skip elements, which are equal to pivot values.
*/
while (a[less] == pivot1) {
- less++;
+ ++less;
}
+
while (a[great] == pivot2) {
- great--;
+ --great;
}
/*
@@ -330,7 +427,7 @@
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) {
@@ -348,12 +445,12 @@
* 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;
}
}
}
@@ -361,7 +458,13 @@
// 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:
@@ -383,35 +486,35 @@
* 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++;
- } else { // a[k] > pivot1 - Move a[k] to right part
- while (a[great] > pivot1) {
- great--;
+ ++less;
+ } else { // a[k] > pivot - Move a[k] to right part
+ while (a[great] > pivot) {
+ --great;
}
- if (a[great] < pivot1) { // a[great] <= pivot1
+ if (a[great] < pivot) { // a[great] <= pivot
a[k] = a[less];
a[less] = a[great];
- less++;
- } else { // a[great] == pivot1
+ ++less;
+ } else { // a[great] == pivot
/*
- * Even though a[great] equals to pivot1, the
- * assignment a[k] = pivot1 may be incorrect,
- * if a[great] and pivot1 are floating-point
+ * Even though a[great] equals to pivot, the
+ * assignment a[k] = pivot may be incorrect,
+ * 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;
}
}
@@ -431,7 +534,7 @@
* @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);
}
/**
@@ -442,7 +545,89 @@
* @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;
+ }
}
/**
@@ -456,7 +641,7 @@
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) {
/*
@@ -479,26 +664,24 @@
* 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
- * sort, which is faster than traditional implementation
- * in the context of Dual-Pivot Quicksort.
+ * the more optimized algorithm, so called pair insertion
+ * sort, which is faster (in the context of Quicksort)
+ * than traditional implementation of insertion sort.
*/
- for (int k = left--; (left += 2) <= right; ) {
- long a1, a2; k = left - 1;
+ for (int k = left; ++left <= right; k = ++left) {
+ long a1 = a[k], a2 = a[left];
- if (a[k] < a[left]) {
- a2 = a[k]; a1 = a[left];
- } else {
- a1 = a[k]; a2 = a[left];
+ if (a1 < a2) {
+ a2 = a1; a1 = a[left];
}
while (a1 < a[--k]) {
a[k + 2] = a[k];
@@ -555,19 +738,19 @@
}
}
- /*
- * 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
@@ -612,7 +795,7 @@
* 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) {
@@ -622,7 +805,7 @@
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];
}
@@ -631,7 +814,7 @@
* of "a[i--] = b;" due to performance issue.
*/
a[great] = ak;
- great--;
+ --great;
}
}
@@ -652,10 +835,11 @@
* Skip elements, which are equal to pivot values.
*/
while (a[less] == pivot1) {
- less++;
+ ++less;
}
+
while (a[great] == pivot2) {
- great--;
+ --great;
}
/*
@@ -683,7 +867,7 @@
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) {
@@ -701,12 +885,12 @@
* 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;
}
}
}
@@ -714,7 +898,13 @@
// 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:
@@ -736,35 +926,35 @@
* 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++;
- } else { // a[k] > pivot1 - Move a[k] to right part
- while (a[great] > pivot1) {
- great--;
+ ++less;
+ } else { // a[k] > pivot - Move a[k] to right part
+ while (a[great] > pivot) {
+ --great;
}
- if (a[great] < pivot1) { // a[great] <= pivot1
+ if (a[great] < pivot) { // a[great] <= pivot
a[k] = a[less];
a[less] = a[great];
- less++;
- } else { // a[great] == pivot1
+ ++less;
+ } else { // a[great] == pivot
/*
- * Even though a[great] equals to pivot1, the
- * assignment a[k] = pivot1 may be incorrect,
- * if a[great] and pivot1 are floating-point
+ * Even though a[great] equals to pivot, the
+ * assignment a[k] = pivot may be incorrect,
+ * 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;
}
}
@@ -799,9 +989,9 @@
if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
int[] count = new int[NUM_SHORT_VALUES];
- for (int i = left - 1; ++i <= right; ) {
- count[a[i] - Short.MIN_VALUE]++;
- }
+ for (int i = left - 1; ++i <= right;
+ 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);
@@ -812,7 +1002,7 @@
} while (--s > 0);
}
} else { // Use Dual-Pivot Quicksort on small arrays
- sort(a, left, right, true);
+ doSort(a, left, right);
}
}
@@ -820,6 +1010,99 @@
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
@@ -827,10 +1110,10 @@
* @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) {
/*
@@ -853,26 +1136,24 @@
* 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
- * sort, which is faster than traditional implementation
- * in the context of Dual-Pivot Quicksort.
+ * the more optimized algorithm, so called pair insertion
+ * sort, which is faster (in the context of Quicksort)
+ * than traditional implementation of insertion sort.
*/
- for (int k = left--; (left += 2) <= right; ) {
- short a1, a2; k = left - 1;
+ for (int k = left; ++left <= right; k = ++left) {
+ short a1 = a[k], a2 = a[left];
- if (a[k] < a[left]) {
- a2 = a[k]; a1 = a[left];
- } else {
- a1 = a[k]; a2 = a[left];
+ if (a1 < a2) {
+ a2 = a1; a1 = a[left];
}
while (a1 < a[--k]) {
a[k + 2] = a[k];
@@ -929,19 +1210,19 @@
}
}
- /*
- * 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
@@ -986,7 +1267,7 @@
* 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) {
@@ -996,7 +1277,7 @@
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];
}
@@ -1005,7 +1286,7 @@
* of "a[i--] = b;" due to performance issue.
*/
a[great] = ak;
- great--;
+ --great;
}
}
@@ -1026,10 +1307,11 @@
* Skip elements, which are equal to pivot values.
*/
while (a[less] == pivot1) {
- less++;
+ ++less;
}
+
while (a[great] == pivot2) {
- great--;
+ --great;
}
/*
@@ -1057,7 +1339,7 @@
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) {
@@ -1075,12 +1357,12 @@
* 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;
}
}
}
@@ -1088,7 +1370,13 @@
// 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:
@@ -1110,35 +1398,35 @@
* 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++;
- } else { // a[k] > pivot1 - Move a[k] to right part
- while (a[great] > pivot1) {
- great--;
+ ++less;
+ } else { // a[k] > pivot - Move a[k] to right part
+ while (a[great] > pivot) {
+ --great;
}
- if (a[great] < pivot1) { // a[great] <= pivot1
+ if (a[great] < pivot) { // a[great] <= pivot
a[k] = a[less];
a[less] = a[great];
- less++;
- } else { // a[great] == pivot1
+ ++less;
+ } else { // a[great] == pivot
/*
- * Even though a[great] equals to pivot1, the
- * assignment a[k] = pivot1 may be incorrect,
- * if a[great] and pivot1 are floating-point
+ * Even though a[great] equals to pivot, the
+ * assignment a[k] = pivot may be incorrect,
+ * 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;
}
}
@@ -1173,9 +1461,9 @@
if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
int[] count = new int[NUM_CHAR_VALUES];
- for (int i = left - 1; ++i <= right; ) {
- count[a[i]]++;
- }
+ for (int i = left - 1; ++i <= right;
+ count[a[i]]++
+ );
for (int i = NUM_CHAR_VALUES, k = right + 1; k > left; ) {
while (count[--i] == 0);
char value = (char) i;
@@ -1186,7 +1474,7 @@
} while (--s > 0);
}
} else { // Use Dual-Pivot Quicksort on small arrays
- sort(a, left, right, true);
+ doSort(a, left, right);
}
}
@@ -1194,6 +1482,99 @@
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
@@ -1204,7 +1585,7 @@
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) {
/*
@@ -1227,26 +1608,24 @@
* 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
- * sort, which is faster than traditional implementation
- * in the context of Dual-Pivot Quicksort.
+ * the more optimized algorithm, so called pair insertion
+ * sort, which is faster (in the context of Quicksort)
+ * than traditional implementation of insertion sort.
*/
- for (int k = left--; (left += 2) <= right; ) {
- char a1, a2; k = left - 1;
+ for (int k = left; ++left <= right; k = ++left) {
+ char a1 = a[k], a2 = a[left];
- if (a[k] < a[left]) {
- a2 = a[k]; a1 = a[left];
- } else {
- a1 = a[k]; a2 = a[left];
+ if (a1 < a2) {
+ a2 = a1; a1 = a[left];
}
while (a1 < a[--k]) {
a[k + 2] = a[k];
@@ -1303,19 +1682,19 @@
}
}
- /*
- * 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
@@ -1360,7 +1739,7 @@
* 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) {
@@ -1370,7 +1749,7 @@
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];
}
@@ -1379,7 +1758,7 @@
* of "a[i--] = b;" due to performance issue.
*/
a[great] = ak;
- great--;
+ --great;
}
}
@@ -1400,10 +1779,11 @@
* Skip elements, which are equal to pivot values.
*/
while (a[less] == pivot1) {
- less++;
+ ++less;
}
+
while (a[great] == pivot2) {
- great--;
+ --great;
}
/*
@@ -1431,7 +1811,7 @@
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) {
@@ -1449,12 +1829,12 @@
* 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;
}
}
}
@@ -1462,7 +1842,13 @@
// 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:
@@ -1484,35 +1870,35 @@
* 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++;
- } else { // a[k] > pivot1 - Move a[k] to right part
- while (a[great] > pivot1) {
- great--;
+ ++less;
+ } else { // a[k] > pivot - Move a[k] to right part
+ while (a[great] > pivot) {
+ --great;
}
- if (a[great] < pivot1) { // a[great] <= pivot1
+ if (a[great] < pivot) { // a[great] <= pivot
a[k] = a[less];
a[less] = a[great];
- less++;
- } else { // a[great] == pivot1
+ ++less;
+ } else { // a[great] == pivot
/*
- * Even though a[great] equals to pivot1, the
- * assignment a[k] = pivot1 may be incorrect,
- * if a[great] and pivot1 are floating-point
+ * Even though a[great] equals to pivot, the
+ * assignment a[k] = pivot may be incorrect,
+ * 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;
}
}
@@ -1550,9 +1936,9 @@
if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
int[] count = new int[NUM_BYTE_VALUES];
- for (int i = left - 1; ++i <= right; ) {
- count[a[i] - Byte.MIN_VALUE]++;
- }
+ for (int i = left - 1; ++i <= right;
+ 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);
@@ -1597,21 +1983,21 @@
* 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.
@@ -1636,7 +2022,7 @@
* Skip the last negative value (if any) or all leading negative zeros.
*/
while (left <= right && Float.floatToRawIntBits(a[left]) < 0) {
- left++;
+ ++left;
}
/*
@@ -1673,6 +2059,99 @@
}
/**
+ * 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
@@ -1680,10 +2159,10 @@
* @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) {
/*
@@ -1706,26 +2185,24 @@
* 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
- * sort, which is faster than traditional implementation
- * in the context of Dual-Pivot Quicksort.
+ * the more optimized algorithm, so called pair insertion
+ * sort, which is faster (in the context of Quicksort)
+ * than traditional implementation of insertion sort.
*/
- for (int k = left--; (left += 2) <= right; ) {
- float a1, a2; k = left - 1;
+ for (int k = left; ++left <= right; k = ++left) {
+ float a1 = a[k], a2 = a[left];
- if (a[k] < a[left]) {
- a2 = a[k]; a1 = a[left];
- } else {
- a1 = a[k]; a2 = a[left];
+ if (a1 < a2) {
+ a2 = a1; a1 = a[left];
}
while (a1 < a[--k]) {
a[k + 2] = a[k];
@@ -1782,19 +2259,19 @@
}
}
- /*
- * 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
@@ -1839,7 +2316,7 @@
* 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) {
@@ -1849,7 +2326,7 @@
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];
}
@@ -1858,7 +2335,7 @@
* of "a[i--] = b;" due to performance issue.
*/
a[great] = ak;
- great--;
+ --great;
}
}
@@ -1879,10 +2356,11 @@
* Skip elements, which are equal to pivot values.
*/
while (a[less] == pivot1) {
- less++;
+ ++less;
}
+
while (a[great] == pivot2) {
- great--;
+ --great;
}
/*
@@ -1910,7 +2388,7 @@
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) {
@@ -1928,12 +2406,12 @@
* 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;
}
}
}
@@ -1941,7 +2419,13 @@
// 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:
@@ -1963,27 +2447,27 @@
* 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++;
- } else { // a[k] > pivot1 - Move a[k] to right part
- while (a[great] > pivot1) {
- great--;
+ ++less;
+ } else { // a[k] > pivot - Move a[k] to right part
+ while (a[great] > pivot) {
+ --great;
}
- if (a[great] < pivot1) { // a[great] <= pivot1
+ if (a[great] < pivot) { // a[great] <= pivot
a[k] = a[less];
a[less] = a[great];
- less++;
- } else { // a[great] == pivot1
+ ++less;
+ } else { // a[great] == pivot
/*
- * Even though a[great] equals to pivot1, the
- * assignment a[k] = pivot1 may be incorrect,
- * if a[great] and pivot1 are floating-point
+ * Even though a[great] equals to pivot, the
+ * assignment a[k] = pivot may be incorrect,
+ * 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].
@@ -1991,7 +2475,7 @@
a[k] = a[great];
}
a[great] = ak;
- great--;
+ --great;
}
}
@@ -2026,21 +2510,21 @@
* 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.
@@ -2065,7 +2549,7 @@
* Skip the last negative value (if any) or all leading negative zeros.
*/
while (left <= right && Double.doubleToRawLongBits(a[left]) < 0) {
- left++;
+ ++left;
}
/*
@@ -2102,6 +2586,99 @@
}
/**
+ * 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
@@ -2109,10 +2686,10 @@
* @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) {
/*
@@ -2135,26 +2712,24 @@
* 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
- * sort, which is faster than traditional implementation
- * in the context of Dual-Pivot Quicksort.
+ * the more optimized algorithm, so called pair insertion
+ * sort, which is faster (in the context of Quicksort)
+ * than traditional implementation of insertion sort.
*/
- for (int k = left--; (left += 2) <= right; ) {
- double a1, a2; k = left - 1;
+ for (int k = left; ++left <= right; k = ++left) {
+ double a1 = a[k], a2 = a[left];
- if (a[k] < a[left]) {
- a2 = a[k]; a1 = a[left];
- } else {
- a1 = a[k]; a2 = a[left];
+ if (a1 < a2) {
+ a2 = a1; a1 = a[left];
}
while (a1 < a[--k]) {
a[k + 2] = a[k];
@@ -2211,19 +2786,19 @@
}
}
- /*
- * 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
@@ -2268,7 +2843,7 @@
* 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) {
@@ -2278,7 +2853,7 @@
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];
}
@@ -2287,7 +2862,7 @@
* of "a[i--] = b;" due to performance issue.
*/
a[great] = ak;
- great--;
+ --great;
}
}
@@ -2308,10 +2883,11 @@
* Skip elements, which are equal to pivot values.
*/
while (a[less] == pivot1) {
- less++;
+ ++less;
}
+
while (a[great] == pivot2) {
- great--;
+ --great;
}
/*
@@ -2339,7 +2915,7 @@
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) {
@@ -2357,12 +2933,12 @@
* 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;
}
}
}
@@ -2370,7 +2946,13 @@
// 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:
@@ -2392,27 +2974,27 @@
* 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++;
- } else { // a[k] > pivot1 - Move a[k] to right part
- while (a[great] > pivot1) {
- great--;
+ ++less;
+ } else { // a[k] > pivot - Move a[k] to right part
+ while (a[great] > pivot) {
+ --great;
}
- if (a[great] < pivot1) { // a[great] <= pivot1
+ if (a[great] < pivot) { // a[great] <= pivot
a[k] = a[less];
a[less] = a[great];
- less++;
- } else { // a[great] == pivot1
+ ++less;
+ } else { // a[great] == pivot
/*
- * Even though a[great] equals to pivot1, the
- * assignment a[k] = pivot1 may be incorrect,
- * if a[great] and pivot1 are floating-point
+ * Even though a[great] equals to pivot, the
+ * assignment a[k] = pivot may be incorrect,
+ * 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].
@@ -2420,7 +3002,7 @@
a[k] = a[great];
}
a[great] = ak;
- great--;
+ --great;
}
}
diff -r cbd5448015d8 -r b90884cf34f5 jdk/test/java/util/Arrays/Sorting.java
--- a/jdk/test/java/util/Arrays/Sorting.java Mon Feb 07 18:02:30 2011 +0000
+++ b/jdk/test/java/util/Arrays/Sorting.java Tue Feb 08 15:50:30 2011 +0000
@@ -23,7 +23,7 @@
/*
* @test
- * @bug 6880672 6896573 6899694 6976036
+ * @bug 6880672 6896573 6899694 6976036 7013585
* @summary Exercise Arrays.sort
* @build Sorting
* @run main Sorting -shortrun
@@ -546,13 +546,19 @@
private static void prepareSubArray(int[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
- a[i] = 0xBABA;
+ a[i] = 0xDEDA;
}
- for (int i = fromIndex; i < toIndex; i++) {
- a[i] = -i + m;
+ int middle = (fromIndex + toIndex) >>> 1;
+ int k = 0;
+
+ for (int i = fromIndex; i < middle; i++) {
+ a[i] = k++;
+ }
+ for (int i = middle; i < toIndex; i++) {
+ a[i] = k--;
}
for (int i = toIndex; i < a.length; i++) {
- a[i] = 0xDEDA;
+ a[i] = 0xBABA;
}
}
@@ -1518,9 +1524,9 @@
private static void checkSubArray(Integer[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
- if (a[i].intValue() != 0xBABA) {
+ if (a[i].intValue() != 0xDEDA) {
failed("Range sort changes left element on position " + i +
- ": " + a[i] + ", must be " + 0xBABA);
+ ": " + a[i] + ", must be " + 0xDEDA);
}
}
@@ -1531,18 +1537,18 @@
}
for (int i = toIndex; i < a.length; i++) {
- if (a[i].intValue() != 0xDEDA) {
+ if (a[i].intValue() != 0xBABA) {
failed("Range sort changes right element on position " + i +
- ": " + a[i] + ", must be " + 0xDEDA);
+ ": " + a[i] + ", must be " + 0xBABA);
}
}
}
private static void checkSubArray(int[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
- if (a[i] != 0xBABA) {
+ if (a[i] != 0xDEDA) {
failed("Range sort changes left element on position " + i +
- ": " + a[i] + ", must be " + 0xBABA);
+ ": " + a[i] + ", must be " + 0xDEDA);
}
}
@@ -1553,18 +1559,18 @@
}
for (int i = toIndex; i < a.length; i++) {
- if (a[i] != 0xDEDA) {
+ if (a[i] != 0xBABA) {
failed("Range sort changes right element on position " + i +
- ": " + a[i] + ", must be " + 0xDEDA);
+ ": " + a[i] + ", must be " + 0xBABA);
}
}
}
private static void checkSubArray(byte[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
- if (a[i] != (byte) 0xBABA) {
+ if (a[i] != (byte) 0xDEDA) {
failed("Range sort changes left element on position " + i +
- ": " + a[i] + ", must be " + 0xBABA);
+ ": " + a[i] + ", must be " + 0xDEDA);
}
}
@@ -1575,18 +1581,18 @@
}
for (int i = toIndex; i < a.length; i++) {
- if (a[i] != (byte) 0xDEDA) {
+ if (a[i] != (byte) 0xBABA) {
failed("Range sort changes right element on position " + i +
- ": " + a[i] + ", must be " + 0xDEDA);
+ ": " + a[i] + ", must be " + 0xBABA);
}
}
}
private static void checkSubArray(long[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
- if (a[i] != (long) 0xBABA) {
+ if (a[i] != (long) 0xDEDA) {
failed("Range sort changes left element on position " + i +
- ": " + a[i] + ", must be " + 0xBABA);
+ ": " + a[i] + ", must be " + 0xDEDA);
}
}
@@ -1597,18 +1603,18 @@
}
for (int i = toIndex; i < a.length; i++) {
- if (a[i] != (long) 0xDEDA) {
+ if (a[i] != (long) 0xBABA) {
failed("Range sort changes right element on position " + i +
- ": " + a[i] + ", must be " + 0xDEDA);
+ ": " + a[i] + ", must be " + 0xBABA);
}
}
}
private static void checkSubArray(char[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
- if (a[i] != (char) 0xBABA) {
+ if (a[i] != (char) 0xDEDA) {
failed("Range sort changes left element on position " + i +
- ": " + a[i] + ", must be " + 0xBABA);
+ ": " + a[i] + ", must be " + 0xDEDA);
}
}
@@ -1619,18 +1625,18 @@
}
for (int i = toIndex; i < a.length; i++) {
- if (a[i] != (char) 0xDEDA) {
+ if (a[i] != (char) 0xBABA) {
failed("Range sort changes right element on position " + i +
- ": " + a[i] + ", must be " + 0xDEDA);
+ ": " + a[i] + ", must be " + 0xBABA);
}
}
}
private static void checkSubArray(short[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
- if (a[i] != (short) 0xBABA) {
+ if (a[i] != (short) 0xDEDA) {
failed("Range sort changes left element on position " + i +
- ": " + a[i] + ", must be " + 0xBABA);
+ ": " + a[i] + ", must be " + 0xDEDA);
}
}
@@ -1641,18 +1647,18 @@
}
for (int i = toIndex; i < a.length; i++) {
- if (a[i] != (short) 0xDEDA) {
+ if (a[i] != (short) 0xBABA) {
failed("Range sort changes right element on position " + i +
- ": " + a[i] + ", must be " + 0xDEDA);
+ ": " + a[i] + ", must be " + 0xBABA);
}
}
}
private static void checkSubArray(float[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
- if (a[i] != (float) 0xBABA) {
+ if (a[i] != (float) 0xDEDA) {
failed("Range sort changes left element on position " + i +
- ": " + a[i] + ", must be " + 0xBABA);
+ ": " + a[i] + ", must be " + 0xDEDA);
}
}
@@ -1663,18 +1669,18 @@
}
for (int i = toIndex; i < a.length; i++) {
- if (a[i] != (float) 0xDEDA) {
+ if (a[i] != (float) 0xBABA) {
failed("Range sort changes right element on position " + i +
- ": " + a[i] + ", must be " + 0xDEDA);
+ ": " + a[i] + ", must be " + 0xBABA);
}
}
}
private static void checkSubArray(double[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
- if (a[i] != (double) 0xBABA) {
+ if (a[i] != (double) 0xDEDA) {
failed("Range sort changes left element on position " + i +
- ": " + a[i] + ", must be " + 0xBABA);
+ ": " + a[i] + ", must be " + 0xDEDA);
}
}
@@ -1685,9 +1691,9 @@
}
for (int i = toIndex; i < a.length; i++) {
- if (a[i] != (double) 0xDEDA) {
+ if (a[i] != (double) 0xBABA) {
failed("Range sort changes right element on position " + i +
- ": " + a[i] + ", must be " + 0xDEDA);
+ ": " + a[i] + ", must be " + 0xBABA);
}
}
}