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

equal deleted inserted replaced

-:3cb70d5832aa
+:b56c69500af6
 * 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
 /*
 * Sorting methods for seven primitive types.
 */
 /**
-* Sorts the specified array.
+* Sorts the specified range of the array using the given
-*
+* workspace array slice if possible for merging
-* @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
+* @param work a workspace array (slice)
+* @param workBase origin of usable space in work array
+* @param workLen usable size of work array
 */
-public static void sort(int[] a, int left, int right) {
+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;
 }
 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
-* Create temporary array, which is used for merging.
+byte odd = 0;
-* Implementation note: variable "right" is increased by 1.
-*/
-int[] b; 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) {
-b = a; a = new int[b.length];
+System.arraycopy(a, left, work, workBase, blen);
-for (int i = left - 1; ++i < right; a[i] = b[i]);
+b = a;
+bo = 0;
+a = work;
+ao = workBase - left;
 } else {
-b = new int[a.length];
+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] <= a[q]) {
+if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
-b[i] = a[p++];
+b[i + bo] = a[p++ + ao];
 } else {
-b[i] = a[q++];
+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] = a[i]
+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.
 sort(a, great + 1, right, false);
 }
 }
 /**
-* Sorts the specified array.
+* Sorts the specified range of the array using the given
-*
+* workspace array slice if possible for merging
-* @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
+* @param work a workspace array (slice)
+* @param workBase origin of usable space in work array
+* @param workLen usable size of work array
 */
-public static void sort(long[] a, int left, int right) {
+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;
 }
 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
-* Create temporary array, which is used for merging.
+byte odd = 0;
-* Implementation note: variable "right" is increased by 1.
-*/
-long[] b; 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) {
-b = a; a = new long[b.length];
+System.arraycopy(a, left, work, workBase, blen);
-for (int i = left - 1; ++i < right; a[i] = b[i]);
+b = a;
+bo = 0;
+a = work;
+ao = workBase - left;
 } else {
-b = new long[a.length];
+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] <= a[q]) {
+if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
-b[i] = a[p++];
+b[i + bo] = a[p++ + ao];
 } else {
-b[i] = a[q++];
+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] = a[i]
+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.
 sort(a, great + 1, right, false);
 }
 }
 /**
-* Sorts the specified array.
+* Sorts the specified range of the array using the given
-*
+* workspace array slice if possible for merging
-* @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
+* @param work a workspace array (slice)
+* @param workBase origin of usable space in work array
+* @param workLen usable size of work array
 */
-public static void sort(short[] a, int left, int right) {
+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;
 do {
 a[--k] = value;
 } while (--s > 0);
 }
 } else { // Use Dual-Pivot Quicksort on small arrays
-doSort(a, left, right);
+doSort(a, left, right, work, workBase, workLen);
 }
 }
 /** 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
+* @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) {
+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;
 }
 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
-* Create temporary array, which is used for merging.
+byte odd = 0;
-* Implementation note: variable "right" is increased by 1.
-*/
-short[] b; 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) {
-b = a; a = new short[b.length];
+System.arraycopy(a, left, work, workBase, blen);
-for (int i = left - 1; ++i < right; a[i] = b[i]);
+b = a;
+bo = 0;
+a = work;
+ao = workBase - left;
 } else {
-b = new short[a.length];
+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] <= a[q]) {
+if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
-b[i] = a[p++];
+b[i + bo] = a[p++ + ao];
 } else {
-b[i] = a[q++];
+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] = a[i]
+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.
 sort(a, great + 1, right, false);
 }
 }
 /**
-* Sorts the specified array.
+* Sorts the specified range of the array using the given
-*
+* workspace array slice if possible for merging
-* @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
+* @param work a workspace array (slice)
+* @param workBase origin of usable space in work array
+* @param workLen usable size of work array
 */
-public static void sort(char[] a, int left, int right) {
+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;
 do {
 a[--k] = value;
 } while (--s > 0);
 }
 } else { // Use Dual-Pivot Quicksort on small arrays
-doSort(a, left, right);
+doSort(a, left, right, work, workBase, workLen);
 }
 }
 /** 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
+* @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) {
+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;
 }
 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
-* Create temporary array, which is used for merging.
+byte odd = 0;
-* Implementation note: variable "right" is increased by 1.
-*/
-char[] b; 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) {
-b = a; a = new char[b.length];
+System.arraycopy(a, left, work, workBase, blen);
-for (int i = left - 1; ++i < right; a[i] = b[i]);
+b = a;
+bo = 0;
+a = work;
+ao = workBase - left;
 } else {
-b = new char[a.length];
+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] <= a[q]) {
+if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
-b[i] = a[p++];
+b[i + bo] = a[p++ + ao];
 } else {
-b[i] = a[q++];
+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] = a[i]
+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.
 /** 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) {
+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;
 }
 }
 }
 /**
-* Sorts the specified array.
+* Sorts the specified range of the array using the given
-*
+* workspace array slice if possible for merging
-* @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
+* @param work a workspace array (slice)
+* @param workBase origin of usable space in work array
+* @param workLen usable size of work array
 */
-public static void sort(float[] a, int left, int right) {
+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;
 }
 /*
 * Phase 2: Sort everything except NaNs (which are already in place).
 */
-doSort(a, left, right);
+doSort(a, left, right, work, workBase, workLen);
 /*
 * Phase 3: Place negative zeros before positive zeros.
 */
 int hi = right;
 * 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) {
+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;
 }
 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
-* Create temporary array, which is used for merging.
+byte odd = 0;
-* Implementation note: variable "right" is increased by 1.
-*/
-float[] b; 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) {
-b = a; a = new float[b.length];
+System.arraycopy(a, left, work, workBase, blen);
-for (int i = left - 1; ++i < right; a[i] = b[i]);
+b = a;
+bo = 0;
+a = work;
+ao = workBase - left;
 } else {
-b = new float[a.length];
+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] <= a[q]) {
+if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
-b[i] = a[p++];
+b[i + bo] = a[p++ + ao];
 } else {
-b[i] = a[q++];
+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] = a[i]
+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.
 sort(a, great + 1, right, false);
 }
 }
 /**
-* Sorts the specified array.
+* Sorts the specified range of the array using the given
-*
+* workspace array slice if possible for merging
-* @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
+* @param work a workspace array (slice)
+* @param workBase origin of usable space in work array
+* @param workLen usable size of work array
 */
-public static void sort(double[] a, int left, int right) {
+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;
 }
 /*
 * Phase 2: Sort everything except NaNs (which are already in place).
 */
-doSort(a, left, right);
+doSort(a, left, right, work, workBase, workLen);
 /*
 * Phase 3: Place negative zeros before positive zeros.
 */
 int hi = right;
 * 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) {
+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;
 }
 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
-* Create temporary array, which is used for merging.
+byte odd = 0;
-* Implementation note: variable "right" is increased by 1.
-*/
-double[] b; 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) {
-b = a; a = new double[b.length];
+System.arraycopy(a, left, work, workBase, blen);
-for (int i = left - 1; ++i < right; a[i] = b[i]);
+b = a;
+bo = 0;
+a = work;
+ao = workBase - left;
 } else {
-b = new double[a.length];
+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] <= a[q]) {
+if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
-b[i] = a[p++];
+b[i + bo] = a[p++ + ao];
 } else {
-b[i] = a[q++];
+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] = a[i]
+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.

changeset 17712	b56c69500af6
parent 9035	1255eb81cc2f
child 23010	6dadb192ad81