--- a/jdk/src/share/classes/java/util/Arrays.java Wed Jul 29 13:56:15 2009 -0700
+++ b/jdk/src/share/classes/java/util/Arrays.java Wed Jul 29 14:24:19 2009 -0700
@@ -1065,29 +1065,103 @@
(x[b] > x[c] ? b : x[a] > x[c] ? c : a));
}
+ /**
+ * Old merge sort implementation can be selected (for
+ * compatibility with broken comparators) using a system property.
+ * Cannot be a static boolean in the enclosing class due to
+ * circular dependencies. To be removed in a future release.
+ */
+ static final class LegacyMergeSort {
+ private static final boolean userRequested =
+ java.security.AccessController.doPrivileged(
+ new sun.security.action.GetBooleanAction(
+ "java.util.Arrays.useLegacyMergeSort")).booleanValue();
+ }
+
+ /*
+ * If this platform has an optimizing VM, check whether ComparableTimSort
+ * offers any performance benefit over TimSort in conjunction with a
+ * comparator that returns:
+ * {@code ((Comparable)first).compareTo(Second)}.
+ * If not, you are better off deleting ComparableTimSort to
+ * eliminate the code duplication. In other words, the commented
+ * out code below is the preferable implementation for sorting
+ * arrays of Comparables if it offers sufficient performance.
+ */
+
+// /**
+// * A comparator that implements the natural ordering of a group of
+// * mutually comparable elements. Using this comparator saves us
+// * from duplicating most of the code in this file (one version for
+// * Comparables, one for explicit Comparators).
+// */
+// private static final Comparator<Object> NATURAL_ORDER =
+// new Comparator<Object>() {
+// @SuppressWarnings("unchecked")
+// public int compare(Object first, Object second) {
+// return ((Comparable<Object>)first).compareTo(second);
+// }
+// };
+//
+// public static void sort(Object[] a) {
+// sort(a, 0, a.length, NATURAL_ORDER);
+// }
+//
+// public static void sort(Object[] a, int fromIndex, int toIndex) {
+// sort(a, fromIndex, toIndex, NATURAL_ORDER);
+// }
/**
- * Sorts the specified array of objects into ascending order, according to
- * the {@linkplain Comparable natural ordering}
- * of its elements. All elements in the array
- * must implement the {@link Comparable} interface. Furthermore, all
- * elements in the array must be <i>mutually comparable</i> (that is,
- * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
- * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p>
+ * Sorts the specified array of objects into ascending order, according
+ * to the {@linkplain Comparable natural ordering} of its elements.
+ * All elements in the array must implement the {@link Comparable}
+ * interface. Furthermore, all elements in the array must be
+ * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must
+ * not throw a {@code ClassCastException} for any elements {@code e1}
+ * and {@code e2} in the array).
+ *
+ * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
+ * not be reordered as a result of the sort.
*
- * This sort is guaranteed to be <i>stable</i>: equal elements will
- * not be reordered as a result of the sort.<p>
+ * <p>Implementation note: This implementation is a stable, adaptive,
+ * iterative mergesort that requires far fewer than n lg(n) comparisons
+ * when the input array is partially sorted, while offering the
+ * performance of a traditional mergesort when the input array is
+ * randomly ordered. If the input array is nearly sorted, the
+ * implementation requires approximately n comparisons. Temporary
+ * storage requirements vary from a small constant for nearly sorted
+ * input arrays to n/2 object references for randomly ordered input
+ * arrays.
*
- * The sorting algorithm is a modified mergesort (in which the merge is
- * omitted if the highest element in the low sublist is less than the
- * lowest element in the high sublist). This algorithm offers guaranteed
- * n*log(n) performance.
+ * <p>The implementation takes equal advantage of ascending and
+ * descending order in its input array, and can take advantage of
+ * ascending and descending order in different parts of the the same
+ * input array. It is well-suited to merging two or more sorted arrays:
+ * simply concatenate the arrays and sort the resulting array.
+ *
+ * <p>The implementation was adapted from Tim Peters's list sort for Python
+ * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
+ * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
+ * Sorting and Information Theoretic Complexity", in Proceedings of the
+ * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
+ * January 1993.
*
* @param a the array to be sorted
- * @throws ClassCastException if the array contains elements that are not
- * <i>mutually comparable</i> (for example, strings and integers).
+ * @throws ClassCastException if the array contains elements that are not
+ * <i>mutually comparable</i> (for example, strings and integers)
+ * @throws IllegalArgumentException (optional) if the natural
+ * ordering of the array elements is found to violate the
+ * {@link Comparable} contract
*/
public static void sort(Object[] a) {
+ if (LegacyMergeSort.userRequested)
+ legacyMergeSort(a);
+ else
+ ComparableTimSort.sort(a);
+ }
+
+ /** To be removed in a future release. */
+ private static void legacyMergeSort(Object[] a) {
Object[] aux = a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
@@ -1097,34 +1171,63 @@
* ascending order, according to the
* {@linkplain Comparable natural ordering} of its
* elements. The range to be sorted extends from index
- * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
- * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.) All
+ * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive.
+ * (If {@code fromIndex==toIndex}, the range to be sorted is empty.) All
* elements in this range must implement the {@link Comparable}
* interface. Furthermore, all elements in this range must be <i>mutually
- * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
- * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
- * <tt>e2</tt> in the array).<p>
+ * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a
+ * {@code ClassCastException} for any elements {@code e1} and
+ * {@code e2} in the array).
+ *
+ * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
+ * not be reordered as a result of the sort.
*
- * This sort is guaranteed to be <i>stable</i>: equal elements will
- * not be reordered as a result of the sort.<p>
+ * <p>Implementation note: This implementation is a stable, adaptive,
+ * iterative mergesort that requires far fewer than n lg(n) comparisons
+ * when the input array is partially sorted, while offering the
+ * performance of a traditional mergesort when the input array is
+ * randomly ordered. If the input array is nearly sorted, the
+ * implementation requires approximately n comparisons. Temporary
+ * storage requirements vary from a small constant for nearly sorted
+ * input arrays to n/2 object references for randomly ordered input
+ * arrays.
*
- * The sorting algorithm is a modified mergesort (in which the merge is
- * omitted if the highest element in the low sublist is less than the
- * lowest element in the high sublist). This algorithm offers guaranteed
- * n*log(n) performance.
+ * <p>The implementation takes equal advantage of ascending and
+ * descending order in its input array, and can take advantage of
+ * ascending and descending order in different parts of the the same
+ * input array. It is well-suited to merging two or more sorted arrays:
+ * simply concatenate the arrays and sort the resulting array.
+ *
+ * <p>The implementation was adapted from Tim Peters's list sort for Python
+ * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
+ * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
+ * Sorting and Information Theoretic Complexity", in Proceedings of the
+ * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
+ * January 1993.
*
* @param a the array to be sorted
* @param fromIndex the index of the first element (inclusive) to be
* sorted
* @param toIndex the index of the last element (exclusive) to be sorted
- * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
- * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
- * <tt>toIndex > a.length</tt>
- * @throws ClassCastException if the array contains elements that are
- * not <i>mutually comparable</i> (for example, strings and
- * integers).
+ * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
+ * (optional) if the natural ordering of the array elements is
+ * found to violate the {@link Comparable} contract
+ * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
+ * {@code toIndex > a.length}
+ * @throws ClassCastException if the array contains elements that are
+ * not <i>mutually comparable</i> (for example, strings and
+ * integers).
*/
public static void sort(Object[] a, int fromIndex, int toIndex) {
+ if (LegacyMergeSort.userRequested)
+ legacyMergeSort(a, fromIndex, toIndex);
+ else
+ ComparableTimSort.sort(a, fromIndex, toIndex);
+ }
+
+ /** To be removed in a future release. */
+ private static void legacyMergeSort(Object[] a,
+ int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
Object[] aux = copyOfRange(a, fromIndex, toIndex);
mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
@@ -1133,6 +1236,7 @@
/**
* Tuning parameter: list size at or below which insertion sort will be
* used in preference to mergesort or quicksort.
+ * To be removed in a future release.
*/
private static final int INSERTIONSORT_THRESHOLD = 7;
@@ -1142,6 +1246,7 @@
* low is the index in dest to start sorting
* high is the end index in dest to end sorting
* off is the offset to generate corresponding low, high in src
+ * To be removed in a future release.
*/
private static void mergeSort(Object[] src,
Object[] dest,
@@ -1197,25 +1302,53 @@
* Sorts the specified array of objects according to the order induced by
* the specified comparator. All elements in the array must be
* <i>mutually comparable</i> by the specified comparator (that is,
- * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
- * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p>
+ * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
+ * for any elements {@code e1} and {@code e2} in the array).
+ *
+ * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
+ * not be reordered as a result of the sort.
*
- * This sort is guaranteed to be <i>stable</i>: equal elements will
- * not be reordered as a result of the sort.<p>
+ * <p>Implementation note: This implementation is a stable, adaptive,
+ * iterative mergesort that requires far fewer than n lg(n) comparisons
+ * when the input array is partially sorted, while offering the
+ * performance of a traditional mergesort when the input array is
+ * randomly ordered. If the input array is nearly sorted, the
+ * implementation requires approximately n comparisons. Temporary
+ * storage requirements vary from a small constant for nearly sorted
+ * input arrays to n/2 object references for randomly ordered input
+ * arrays.
*
- * The sorting algorithm is a modified mergesort (in which the merge is
- * omitted if the highest element in the low sublist is less than the
- * lowest element in the high sublist). This algorithm offers guaranteed
- * n*log(n) performance.
+ * <p>The implementation takes equal advantage of ascending and
+ * descending order in its input array, and can take advantage of
+ * ascending and descending order in different parts of the the same
+ * input array. It is well-suited to merging two or more sorted arrays:
+ * simply concatenate the arrays and sort the resulting array.
+ *
+ * <p>The implementation was adapted from Tim Peters's list sort for Python
+ * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
+ * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
+ * Sorting and Information Theoretic Complexity", in Proceedings of the
+ * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
+ * January 1993.
*
* @param a the array to be sorted
* @param c the comparator to determine the order of the array. A
- * <tt>null</tt> value indicates that the elements'
+ * {@code null} value indicates that the elements'
* {@linkplain Comparable natural ordering} should be used.
- * @throws ClassCastException if the array contains elements that are
- * not <i>mutually comparable</i> using the specified comparator.
+ * @throws ClassCastException if the array contains elements that are
+ * not <i>mutually comparable</i> using the specified comparator
+ * @throws IllegalArgumentException (optional) if the comparator is
+ * found to violate the {@link Comparator} contract
*/
public static <T> void sort(T[] a, Comparator<? super T> c) {
+ if (LegacyMergeSort.userRequested)
+ legacyMergeSort(a, c);
+ else
+ TimSort.sort(a, c);
+ }
+
+ /** To be removed in a future release. */
+ private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) {
T[] aux = a.clone();
if (c==null)
mergeSort(aux, a, 0, a.length, 0);
@@ -1226,36 +1359,65 @@
/**
* Sorts the specified range of the specified array of objects according
* to the order induced by the specified comparator. The range to be
- * sorted extends from index <tt>fromIndex</tt>, inclusive, to index
- * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
+ * sorted extends from index {@code fromIndex}, inclusive, to index
+ * {@code toIndex}, exclusive. (If {@code fromIndex==toIndex}, the
* range to be sorted is empty.) All elements in the range must be
* <i>mutually comparable</i> by the specified comparator (that is,
- * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
- * for any elements <tt>e1</tt> and <tt>e2</tt> in the range).<p>
+ * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
+ * for any elements {@code e1} and {@code e2} in the range).
+ *
+ * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
+ * not be reordered as a result of the sort.
*
- * This sort is guaranteed to be <i>stable</i>: equal elements will
- * not be reordered as a result of the sort.<p>
+ * <p>Implementation note: This implementation is a stable, adaptive,
+ * iterative mergesort that requires far fewer than n lg(n) comparisons
+ * when the input array is partially sorted, while offering the
+ * performance of a traditional mergesort when the input array is
+ * randomly ordered. If the input array is nearly sorted, the
+ * implementation requires approximately n comparisons. Temporary
+ * storage requirements vary from a small constant for nearly sorted
+ * input arrays to n/2 object references for randomly ordered input
+ * arrays.
*
- * The sorting algorithm is a modified mergesort (in which the merge is
- * omitted if the highest element in the low sublist is less than the
- * lowest element in the high sublist). This algorithm offers guaranteed
- * n*log(n) performance.
+ * <p>The implementation takes equal advantage of ascending and
+ * descending order in its input array, and can take advantage of
+ * ascending and descending order in different parts of the the same
+ * input array. It is well-suited to merging two or more sorted arrays:
+ * simply concatenate the arrays and sort the resulting array.
+ *
+ * <p>The implementation was adapted from Tim Peters's list sort for Python
+ * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
+ * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
+ * Sorting and Information Theoretic Complexity", in Proceedings of the
+ * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
+ * January 1993.
*
* @param a the array to be sorted
* @param fromIndex the index of the first element (inclusive) to be
* sorted
* @param toIndex the index of the last element (exclusive) to be sorted
* @param c the comparator to determine the order of the array. A
- * <tt>null</tt> value indicates that the elements'
+ * {@code null} value indicates that the elements'
* {@linkplain Comparable natural ordering} should be used.
* @throws ClassCastException if the array contains elements that are not
* <i>mutually comparable</i> using the specified comparator.
- * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
- * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
- * <tt>toIndex > a.length</tt>
+ * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
+ * (optional) if the comparator is found to violate the
+ * {@link Comparator} contract
+ * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
+ * {@code toIndex > a.length}
*/
public static <T> void sort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c) {
+ if (LegacyMergeSort.userRequested)
+ legacyMergeSort(a, fromIndex, toIndex, c);
+ else
+ TimSort.sort(a, fromIndex, toIndex, c);
+ }
+
+ /** To be removed in a future release. */
+ private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,
+ Comparator<? super T> c) {
rangeCheck(a.length, fromIndex, toIndex);
T[] aux = copyOfRange(a, fromIndex, toIndex);
if (c==null)
@@ -1270,6 +1432,7 @@
* low is the index in dest to start sorting
* high is the end index in dest to end sorting
* off is the offset into src corresponding to low in dest
+ * To be removed in a future release.
*/
private static void mergeSort(Object[] src,
Object[] dest,