src/share/classes/java/util/DualPivotQuicksort.java
Print this page
*** 30,39 ****
--- 30,44 ----
* Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
+ * All exposed methods are package-private, designed to be invoked
+ * from public methods (in class Arrays) after performing any
+ * necessary array bounds checks and expanding parameters into the
+ * required forms.
+ *
* @author Vladimir Yaroslavskiy
* @author Jon Bentley
* @author Josh Bloch
*
* @version 2011.02.11 m765.827.12i:5\7pm
*** 87,112 ****
/*
* Sorting methods for seven primitive types.
*/
/**
! * Sorts the specified array.
*
* @param a the array to be sorted
- */
- public static void sort(int[] a) {
- 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) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
--- 92,113 ----
/*
* Sorting methods for seven primitive types.
*/
/**
! * Sorts the specified range of the array using the given
! * workspace array slice if possible for merging
*
* @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 work a workspace array (slice)
+ * @param workBase origin of usable space in work array
+ * @param workLen usable size of work array
*/
! static void sort(int[] a, int left, int right,
! int[] work, int workBase, int workLen) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
*** 145,194 ****
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.
--- 146,207 ----
return;
}
}
// Check special cases
+ // Implementation note: variable "right" is increased by 1.
if (run[count] == right++) { // The last run contains one element
run[++count] = right;
} else if (count == 1) { // The array is already sorted
return;
}
! // Determine alternation base for merge
! byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);
+ // Use or create temporary array b for merging
+ int[] b; // temp array; alternates with a
+ int ao, bo; // array offsets from 'left'
+ int blen = right - left; // space needed for b
+ if (work == null || workLen < blen || workBase + blen > work.length) {
+ work = new int[blen];
+ workBase = 0;
+ }
if (odd == 0) {
! System.arraycopy(a, left, work, workBase, blen);
! b = a;
! bo = 0;
! a = work;
! ao = workBase - left;
} else {
! b = work;
! ao = 0;
! bo = workBase - left;
}
// 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 + ao] <= a[q + ao]) {
! b[i + bo] = a[p++ + ao];
} else {
! b[i + bo] = a[q++ + ao];
}
}
run[++last] = hi;
}
if ((count & 1) != 0) {
for (int i = right, lo = run[count - 1]; --i >= lo;
! b[i + bo] = a[i + ao]
);
run[++last] = right;
}
int[] t = a; a = b; b = t;
+ int o = ao; ao = bo; bo = o;
}
}
/**
* Sorts the specified range of the array by Dual-Pivot Quicksort.
*** 527,552 ****
sort(a, great + 1, right, false);
}
}
/**
! * Sorts the specified array.
*
* @param a the array to be sorted
- */
- public static void sort(long[] a) {
- 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) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
--- 540,561 ----
sort(a, great + 1, right, false);
}
}
/**
! * Sorts the specified range of the array using the given
! * workspace array slice if possible for merging
*
* @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 work a workspace array (slice)
+ * @param workBase origin of usable space in work array
+ * @param workLen usable size of work array
*/
! static void sort(long[] a, int left, int right,
! long[] work, int workBase, int workLen) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
*** 585,634 ****
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.
--- 594,655 ----
return;
}
}
// Check special cases
+ // Implementation note: variable "right" is increased by 1.
if (run[count] == right++) { // The last run contains one element
run[++count] = right;
} else if (count == 1) { // The array is already sorted
return;
}
! // Determine alternation base for merge
! byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);
+ // Use or create temporary array b for merging
+ long[] b; // temp array; alternates with a
+ int ao, bo; // array offsets from 'left'
+ int blen = right - left; // space needed for b
+ if (work == null || workLen < blen || workBase + blen > work.length) {
+ work = new long[blen];
+ workBase = 0;
+ }
if (odd == 0) {
! System.arraycopy(a, left, work, workBase, blen);
! b = a;
! bo = 0;
! a = work;
! ao = workBase - left;
} else {
! b = work;
! ao = 0;
! bo = workBase - left;
}
// 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 + ao] <= a[q + ao]) {
! b[i + bo] = a[p++ + ao];
} else {
! b[i + bo] = a[q++ + ao];
}
}
run[++last] = hi;
}
if ((count & 1) != 0) {
for (int i = right, lo = run[count - 1]; --i >= lo;
! b[i + bo] = a[i + ao]
);
run[++last] = right;
}
long[] t = a; a = b; b = t;
+ int o = ao; ao = bo; bo = o;
}
}
/**
* Sorts the specified range of the array by Dual-Pivot Quicksort.
*** 967,992 ****
sort(a, great + 1, right, false);
}
}
/**
! * Sorts the specified array.
*
* @param a the array to be sorted
- */
- public static void sort(short[] a) {
- 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(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;
--- 988,1009 ----
sort(a, great + 1, right, false);
}
}
/**
! * Sorts the specified range of the array using the given
! * workspace array slice if possible for merging
*
* @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 work a workspace array (slice)
+ * @param workBase origin of usable space in work array
+ * @param workLen usable size of work array
*/
! static void sort(short[] a, int left, int right,
! short[] work, int workBase, int workLen) {
// 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;
*** 1000,1010 ****
do {
a[--k] = value;
} while (--s > 0);
}
} else { // Use Dual-Pivot Quicksort on small arrays
! doSort(a, left, right);
}
}
/** The number of distinct short values. */
private static final int NUM_SHORT_VALUES = 1 << 16;
--- 1017,1027 ----
do {
a[--k] = value;
} while (--s > 0);
}
} else { // Use Dual-Pivot Quicksort on small arrays
! doSort(a, left, right, work, workBase, workLen);
}
}
/** The number of distinct short values. */
private static final int NUM_SHORT_VALUES = 1 << 16;
*** 1013,1024 ****
* 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;
}
--- 1030,1045 ----
* 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
+ * @param work a workspace array (slice)
+ * @param workBase origin of usable space in work array
+ * @param workLen usable size of work array
*/
! private static void doSort(short[] a, int left, int right,
! short[] work, int workBase, int workLen) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
*** 1057,1106 ****
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.
--- 1078,1139 ----
return;
}
}
// Check special cases
+ // Implementation note: variable "right" is increased by 1.
if (run[count] == right++) { // The last run contains one element
run[++count] = right;
} else if (count == 1) { // The array is already sorted
return;
}
! // Determine alternation base for merge
! byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);
+ // Use or create temporary array b for merging
+ short[] b; // temp array; alternates with a
+ int ao, bo; // array offsets from 'left'
+ int blen = right - left; // space needed for b
+ if (work == null || workLen < blen || workBase + blen > work.length) {
+ work = new short[blen];
+ workBase = 0;
+ }
if (odd == 0) {
! System.arraycopy(a, left, work, workBase, blen);
! b = a;
! bo = 0;
! a = work;
! ao = workBase - left;
} else {
! b = work;
! ao = 0;
! bo = workBase - left;
}
// 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 + ao] <= a[q + ao]) {
! b[i + bo] = a[p++ + ao];
} else {
! b[i + bo] = a[q++ + ao];
}
}
run[++last] = hi;
}
if ((count & 1) != 0) {
for (int i = right, lo = run[count - 1]; --i >= lo;
! b[i + bo] = a[i + ao]
);
run[++last] = right;
}
short[] t = a; a = b; b = t;
+ int o = ao; ao = bo; bo = o;
}
}
/**
* Sorts the specified range of the array by Dual-Pivot Quicksort.
*** 1439,1464 ****
sort(a, great + 1, right, false);
}
}
/**
! * Sorts the specified array.
*
* @param a the array to be sorted
- */
- public static void sort(char[] a) {
- 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(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;
--- 1472,1493 ----
sort(a, great + 1, right, false);
}
}
/**
! * Sorts the specified range of the array using the given
! * workspace array slice if possible for merging
*
* @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 work a workspace array (slice)
+ * @param workBase origin of usable space in work array
+ * @param workLen usable size of work array
*/
! static void sort(char[] a, int left, int right,
! char[] work, int workBase, int workLen) {
// 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;
*** 1472,1482 ****
do {
a[--k] = value;
} while (--s > 0);
}
} else { // Use Dual-Pivot Quicksort on small arrays
! doSort(a, left, right);
}
}
/** The number of distinct char values. */
private static final int NUM_CHAR_VALUES = 1 << 16;
--- 1501,1511 ----
do {
a[--k] = value;
} while (--s > 0);
}
} else { // Use Dual-Pivot Quicksort on small arrays
! doSort(a, left, right, work, workBase, workLen);
}
}
/** The number of distinct char values. */
private static final int NUM_CHAR_VALUES = 1 << 16;
*** 1485,1496 ****
* 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;
}
--- 1514,1529 ----
* 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
+ * @param work a workspace array (slice)
+ * @param workBase origin of usable space in work array
+ * @param workLen usable size of work array
*/
! private static void doSort(char[] a, int left, int right,
! char[] work, int workBase, int workLen) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
*** 1529,1578 ****
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.
--- 1562,1623 ----
return;
}
}
// Check special cases
+ // Implementation note: variable "right" is increased by 1.
if (run[count] == right++) { // The last run contains one element
run[++count] = right;
} else if (count == 1) { // The array is already sorted
return;
}
! // Determine alternation base for merge
! byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);
+ // Use or create temporary array b for merging
+ char[] b; // temp array; alternates with a
+ int ao, bo; // array offsets from 'left'
+ int blen = right - left; // space needed for b
+ if (work == null || workLen < blen || workBase + blen > work.length) {
+ work = new char[blen];
+ workBase = 0;
+ }
if (odd == 0) {
! System.arraycopy(a, left, work, workBase, blen);
! b = a;
! bo = 0;
! a = work;
! ao = workBase - left;
} else {
! b = work;
! ao = 0;
! bo = workBase - left;
}
// 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 + ao] <= a[q + ao]) {
! b[i + bo] = a[p++ + ao];
} else {
! b[i + bo] = a[q++ + ao];
}
}
run[++last] = hi;
}
if ((count & 1) != 0) {
for (int i = right, lo = run[count - 1]; --i >= lo;
! b[i + bo] = a[i + ao]
);
run[++last] = right;
}
char[] t = a; a = b; b = t;
+ int o = ao; ao = bo; bo = o;
}
}
/**
* Sorts the specified range of the array by Dual-Pivot Quicksort.
*** 1914,1939 ****
/** The number of distinct byte values. */
private static final int NUM_BYTE_VALUES = 1 << 8;
/**
- * Sorts the specified array.
- *
- * @param a the array to be sorted
- */
- public static void sort(byte[] a) {
- 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(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;
--- 1959,1975 ----
/** The number of distinct byte values. */
private static final int NUM_BYTE_VALUES = 1 << 8;
/**
* 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
*/
! 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;
*** 1961,1986 ****
}
}
}
/**
! * Sorts the specified array.
*
* @param a the array to be sorted
- */
- public static void sort(float[] a) {
- 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(float[] a, int left, int right) {
/*
* Phase 1: Move NaNs to the end of the array.
*/
while (left <= right && Float.isNaN(a[right])) {
--right;
--- 1997,2018 ----
}
}
}
/**
! * Sorts the specified range of the array using the given
! * workspace array slice if possible for merging
*
* @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 work a workspace array (slice)
+ * @param workBase origin of usable space in work array
+ * @param workLen usable size of work array
*/
! static void sort(float[] a, int left, int right,
! float[] work, int workBase, int workLen) {
/*
* Phase 1: Move NaNs to the end of the array.
*/
while (left <= right && Float.isNaN(a[right])) {
--right;
*** 1995,2005 ****
}
/*
* Phase 2: Sort everything except NaNs (which are already in place).
*/
! doSort(a, left, right);
/*
* Phase 3: Place negative zeros before positive zeros.
*/
int hi = right;
--- 2027,2037 ----
}
/*
* Phase 2: Sort everything except NaNs (which are already in place).
*/
! doSort(a, left, right, work, workBase, workLen);
/*
* Phase 3: Place negative zeros before positive zeros.
*/
int hi = right;
*** 2062,2073 ****
* 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;
}
--- 2094,2109 ----
* 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
+ * @param work a workspace array (slice)
+ * @param workBase origin of usable space in work array
+ * @param workLen usable size of work array
*/
! private static void doSort(float[] a, int left, int right,
! float[] work, int workBase, int workLen) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
*** 2106,2155 ****
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.
--- 2142,2203 ----
return;
}
}
// Check special cases
+ // Implementation note: variable "right" is increased by 1.
if (run[count] == right++) { // The last run contains one element
run[++count] = right;
} else if (count == 1) { // The array is already sorted
return;
}
! // Determine alternation base for merge
! byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);
+ // Use or create temporary array b for merging
+ float[] b; // temp array; alternates with a
+ int ao, bo; // array offsets from 'left'
+ int blen = right - left; // space needed for b
+ if (work == null || workLen < blen || workBase + blen > work.length) {
+ work = new float[blen];
+ workBase = 0;
+ }
if (odd == 0) {
! System.arraycopy(a, left, work, workBase, blen);
! b = a;
! bo = 0;
! a = work;
! ao = workBase - left;
} else {
! b = work;
! ao = 0;
! bo = workBase - left;
}
// 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 + ao] <= a[q + ao]) {
! b[i + bo] = a[p++ + ao];
} else {
! b[i + bo] = a[q++ + ao];
}
}
run[++last] = hi;
}
if ((count & 1) != 0) {
for (int i = right, lo = run[count - 1]; --i >= lo;
! b[i + bo] = a[i + ao]
);
run[++last] = right;
}
float[] t = a; a = b; b = t;
+ int o = ao; ao = bo; bo = o;
}
}
/**
* Sorts the specified range of the array by Dual-Pivot Quicksort.
*** 2488,2513 ****
sort(a, great + 1, right, false);
}
}
/**
! * Sorts the specified array.
*
* @param a the array to be sorted
- */
- public static void sort(double[] a) {
- 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(double[] a, int left, int right) {
/*
* Phase 1: Move NaNs to the end of the array.
*/
while (left <= right && Double.isNaN(a[right])) {
--right;
--- 2536,2557 ----
sort(a, great + 1, right, false);
}
}
/**
! * Sorts the specified range of the array using the given
! * workspace array slice if possible for merging
*
* @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 work a workspace array (slice)
+ * @param workBase origin of usable space in work array
+ * @param workLen usable size of work array
*/
! static void sort(double[] a, int left, int right,
! double[] work, int workBase, int workLen) {
/*
* Phase 1: Move NaNs to the end of the array.
*/
while (left <= right && Double.isNaN(a[right])) {
--right;
*** 2522,2532 ****
}
/*
* Phase 2: Sort everything except NaNs (which are already in place).
*/
! doSort(a, left, right);
/*
* Phase 3: Place negative zeros before positive zeros.
*/
int hi = right;
--- 2566,2576 ----
}
/*
* Phase 2: Sort everything except NaNs (which are already in place).
*/
! doSort(a, left, right, work, workBase, workLen);
/*
* Phase 3: Place negative zeros before positive zeros.
*/
int hi = right;
*** 2589,2600 ****
* 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;
}
--- 2633,2648 ----
* 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
+ * @param work a workspace array (slice)
+ * @param workBase origin of usable space in work array
+ * @param workLen usable size of work array
*/
! private static void doSort(double[] a, int left, int right,
! double[] work, int workBase, int workLen) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
*** 2633,2682 ****
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.
--- 2681,2742 ----
return;
}
}
// Check special cases
+ // Implementation note: variable "right" is increased by 1.
if (run[count] == right++) { // The last run contains one element
run[++count] = right;
} else if (count == 1) { // The array is already sorted
return;
}
! // Determine alternation base for merge
! byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);
+ // Use or create temporary array b for merging
+ double[] b; // temp array; alternates with a
+ int ao, bo; // array offsets from 'left'
+ int blen = right - left; // space needed for b
+ if (work == null || workLen < blen || workBase + blen > work.length) {
+ work = new double[blen];
+ workBase = 0;
+ }
if (odd == 0) {
! System.arraycopy(a, left, work, workBase, blen);
! b = a;
! bo = 0;
! a = work;
! ao = workBase - left;
} else {
! b = work;
! ao = 0;
! bo = workBase - left;
}
// 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 + ao] <= a[q + ao]) {
! b[i + bo] = a[p++ + ao];
} else {
! b[i + bo] = a[q++ + ao];
}
}
run[++last] = hi;
}
if ((count & 1) != 0) {
for (int i = right, lo = run[count - 1]; --i >= lo;
! b[i + bo] = a[i + ao]
);
run[++last] = right;
}
double[] t = a; a = b; b = t;
+ int o = ao; ao = bo; bo = o;
}
}
/**
* Sorts the specified range of the array by Dual-Pivot Quicksort.