--- a/make/java/java/FILES_java.gmk	Wed Jul 29 13:56:15 2009 -0700
+++ b/make/java/java/FILES_java.gmk	Wed Jul 29 14:24:19 2009 -0700
@@ -250,6 +250,8 @@
 	java/util/IdentityHashMap.java \
 	java/util/EnumMap.java \
     java/util/Arrays.java \
+    java/util/TimSort.java \
+    java/util/ComparableTimSort.java \
     java/util/ConcurrentModificationException.java \
     java/util/ServiceLoader.java \
     java/util/ServiceConfigurationError.java \

--- a/src/share/classes/java/util/Arrays.java	Wed Jul 29 13:56:15 2009 -0700
+++ b/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 &gt; toIndex</tt>
-     * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
-     *         <tt>toIndex &gt; 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 &gt; toIndex</tt>
-     * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
-     *         <tt>toIndex &gt; 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,

--- a/src/share/classes/java/util/Collections.java	Wed Jul 29 13:56:15 2009 -0700
+++ b/src/share/classes/java/util/Collections.java	Wed Jul 29 14:24:19 2009 -0700
@@ -100,23 +100,42 @@
 
     /**
      * Sorts the specified list into ascending order, according to the
-     * <i>natural ordering</i> of its elements.  All elements in the list must
-     * implement the <tt>Comparable</tt> interface.  Furthermore, all elements
-     * in the list 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 list).<p>
+     * {@linkplain Comparable natural ordering} of its elements.
+     * All elements in the list must implement the {@link Comparable}
+     * interface.  Furthermore, all elements in the list 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 list).
      *
-     * This sort is guaranteed to be <i>stable</i>:  equal elements will
-     * not be reordered as a result of the sort.<p>
+     * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
+     * not be reordered as a result of the sort.
+     *
+     * <p>The specified list must be modifiable, but need not be resizable.
      *
-     * The specified list must be modifiable, but need not be resizable.<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.
      *
-     * This implementation dumps the specified list into an array, sorts
+     * <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.
+     *
+     * <p>This implementation dumps the specified list into an array, sorts
      * the array, and iterates over the list resetting each element
      * from the corresponding position in the array.  This avoids the
      * n<sup>2</sup> log(n) performance that would result from attempting
@@ -126,8 +145,10 @@
      * @throws ClassCastException if the list contains elements that are not
      *         <i>mutually comparable</i> (for example, strings and integers).
      * @throws UnsupportedOperationException if the specified list's
-     *         list-iterator does not support the <tt>set</tt> operation.
-     * @see Comparable
+     *         list-iterator does not support the {@code set} operation.
+     * @throws IllegalArgumentException (optional) if the implementation
+     *         detects that the natural ordering of the list elements is
+     *         found to violate the {@link Comparable} contract
      */
     public static <T extends Comparable<? super T>> void sort(List<T> list) {
         Object[] a = list.toArray();
@@ -143,19 +164,38 @@
      * Sorts the specified list according to the order induced by the
      * specified comparator.  All elements in the list must be <i>mutually
      * comparable</i> using 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 list).<p>
+     * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
+     * for any elements {@code e1} and {@code e2} in the list).
      *
-     * This sort is guaranteed to be <i>stable</i>:  equal elements will
-     * not be reordered as a result of the sort.<p>
+     * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
+     * not be reordered as a result of the sort.
+     *
+     * <p>The specified list must be modifiable, but need not be resizable.
      *
-     * 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>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 specified list must be modifiable, but need not be resizable.
-     * This implementation dumps the specified list into an array, sorts
+     * <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.
+     *
+     * <p>This implementation dumps the specified list into an array, sorts
      * the array, and iterates over the list resetting each element
      * from the corresponding position in the array.  This avoids the
      * n<sup>2</sup> log(n) performance that would result from attempting
@@ -163,13 +203,14 @@
      *
      * @param  list the list to be sorted.
      * @param  c the comparator to determine the order of the list.  A
-     *        <tt>null</tt> value indicates that the elements' <i>natural
+     *        {@code null} value indicates that the elements' <i>natural
      *        ordering</i> should be used.
      * @throws ClassCastException if the list contains elements that are not
      *         <i>mutually comparable</i> using the specified comparator.
      * @throws UnsupportedOperationException if the specified list's
-     *         list-iterator does not support the <tt>set</tt> operation.
-     * @see Comparator
+     *         list-iterator does not support the {@code set} operation.
+     * @throws IllegalArgumentException (optional) if the comparator is
+     *         found to violate the {@link Comparator} contract
      */
     public static <T> void sort(List<T> list, Comparator<? super T> c) {
         Object[] a = list.toArray();

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/classes/java/util/ComparableTimSort.java	Wed Jul 29 14:24:19 2009 -0700
@@ -0,0 +1,895 @@
+/*
+ * Copyright 2009 Google Inc.  All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Sun designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Sun in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+
+package java.util;
+
+/**
+ * This is a near duplicate of {@link TimSort}, modified for use with
+ * arrays of objects that implement {@link Comparable}, instead of using
+ * explicit comparators.
+ *
+ * <p>If you are using an optimizing VM, you may find that ComparableTimSort
+ * offers no performance benefit over TimSort in conjunction with a
+ * comparator that simply returns {@code ((Comparable)first).compareTo(Second)}.
+ * If this is the case, you are better off deleting ComparableTimSort to
+ * eliminate the code duplication.  (See Arrays.java for details.)
+ *
+ * @author Josh Bloch
+ */
+class ComparableTimSort {
+    /**
+     * This is the minimum sized sequence that will be merged.  Shorter
+     * sequences will be lengthened by calling binarySort.  If the entire
+     * array is less than this length, no merges will be performed.
+     *
+     * This constant should be a power of two.  It was 64 in Tim Peter's C
+     * implementation, but 32 was empirically determined to work better in
+     * this implementation.  In the unlikely event that you set this constant
+     * to be a number that's not a power of two, you'll need to change the
+     * {@link #minRunLength} computation.
+     *
+     * If you decrease this constant, you must change the stackLen
+     * computation in the TimSort constructor, or you risk an
+     * ArrayOutOfBounds exception.  See listsort.txt for a discussion
+     * of the minimum stack length required as a function of the length
+     * of the array being sorted and the minimum merge sequence length.
+     */
+    private static final int MIN_MERGE = 32;
+
+    /**
+     * The array being sorted.
+     */
+    private final Object[] a;
+
+    /**
+     * When we get into galloping mode, we stay there until both runs win less
+     * often than MIN_GALLOP consecutive times.
+     */
+    private static final int  MIN_GALLOP = 7;
+
+    /**
+     * This controls when we get *into* galloping mode.  It is initialized
+     * to MIN_GALLOP.  The mergeLo and mergeHi methods nudge it higher for
+     * random data, and lower for highly structured data.
+     */
+    private int minGallop = MIN_GALLOP;
+
+    /**
+     * Maximum initial size of tmp array, which is used for merging.  The array
+     * can grow to accommodate demand.
+     *
+     * Unlike Tim's original C version, we do not allocate this much storage
+     * when sorting smaller arrays.  This change was required for performance.
+     */
+    private static final int INITIAL_TMP_STORAGE_LENGTH = 256;
+
+    /**
+     * Temp storage for merges.
+     */
+    private Object[] tmp;
+
+    /**
+     * A stack of pending runs yet to be merged.  Run i starts at
+     * address base[i] and extends for len[i] elements.  It's always
+     * true (so long as the indices are in bounds) that:
+     *
+     *     runBase[i] + runLen[i] == runBase[i + 1]
+     *
+     * so we could cut the storage for this, but it's a minor amount,
+     * and keeping all the info explicit simplifies the code.
+     */
+    private int stackSize = 0;  // Number of pending runs on stack
+    private final int[] runBase;
+    private final int[] runLen;
+
+    /**
+     * Creates a TimSort instance to maintain the state of an ongoing sort.
+     *
+     * @param a the array to be sorted
+     */
+    private ComparableTimSort(Object[] a) {
+        this.a = a;
+
+        // Allocate temp storage (which may be increased later if necessary)
+        int len = a.length;
+        @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
+        Object[] newArray = new Object[len < 2 * INITIAL_TMP_STORAGE_LENGTH ?
+                                       len >>> 1 : INITIAL_TMP_STORAGE_LENGTH];
+        tmp = newArray;
+
+        /*
+         * Allocate runs-to-be-merged stack (which cannot be expanded).  The
+         * stack length requirements are described in listsort.txt.  The C
+         * version always uses the same stack length (85), but this was
+         * measured to be too expensive when sorting "mid-sized" arrays (e.g.,
+         * 100 elements) in Java.  Therefore, we use smaller (but sufficiently
+         * large) stack lengths for smaller arrays.  The "magic numbers" in the
+         * computation below must be changed if MIN_MERGE is decreased.  See
+         * the MIN_MERGE declaration above for more information.
+         */
+        int stackLen = (len <    120  ?  5 :
+                        len <   1542  ? 10 :
+                        len < 119151  ? 19 : 40);
+        runBase = new int[stackLen];
+        runLen = new int[stackLen];
+    }
+
+    /*
+     * The next two methods (which are package private and static) constitute
+     * the entire API of this class.  Each of these methods obeys the contract
+     * of the public method with the same signature in java.util.Arrays.
+     */
+
+    static void sort(Object[] a) {
+          sort(a, 0, a.length);
+    }
+
+    static void sort(Object[] a, int lo, int hi) {
+        rangeCheck(a.length, lo, hi);
+        int nRemaining  = hi - lo;
+        if (nRemaining < 2)
+            return;  // Arrays of size 0 and 1 are always sorted
+
+        // If array is small, do a "mini-TimSort" with no merges
+        if (nRemaining < MIN_MERGE) {
+            int initRunLen = countRunAndMakeAscending(a, lo, hi);
+            binarySort(a, lo, hi, lo + initRunLen);
+            return;
+        }
+
+        /**
+         * March over the array once, left to right, finding natural runs,
+         * extending short natural runs to minRun elements, and merging runs
+         * to maintain stack invariant.
+         */
+        ComparableTimSort ts = new ComparableTimSort(a);
+        int minRun = minRunLength(nRemaining);
+        do {
+            // Identify next run
+            int runLen = countRunAndMakeAscending(a, lo, hi);
+
+            // If run is short, extend to min(minRun, nRemaining)
+            if (runLen < minRun) {
+                int force = nRemaining <= minRun ? nRemaining : minRun;
+                binarySort(a, lo, lo + force, lo + runLen);
+                runLen = force;
+            }
+
+            // Push run onto pending-run stack, and maybe merge
+            ts.pushRun(lo, runLen);
+            ts.mergeCollapse();
+
+            // Advance to find next run
+            lo += runLen;
+            nRemaining -= runLen;
+        } while (nRemaining != 0);
+
+        // Merge all remaining runs to complete sort
+        assert lo == hi;
+        ts.mergeForceCollapse();
+        assert ts.stackSize == 1;
+    }
+
+    /**
+     * Sorts the specified portion of the specified array using a binary
+     * insertion sort.  This is the best method for sorting small numbers
+     * of elements.  It requires O(n log n) compares, but O(n^2) data
+     * movement (worst case).
+     *
+     * If the initial part of the specified range is already sorted,
+     * this method can take advantage of it: the method assumes that the
+     * elements from index {@code lo}, inclusive, to {@code start},
+     * exclusive are already sorted.
+     *
+     * @param a the array in which a range is to be sorted
+     * @param lo the index of the first element in the range to be sorted
+     * @param hi the index after the last element in the range to be sorted
+     * @param start the index of the first element in the range that is
+     *        not already known to be sorted (@code lo <= start <= hi}
+     */
+    @SuppressWarnings("fallthrough")
+    private static void binarySort(Object[] a, int lo, int hi, int start) {
+        assert lo <= start && start <= hi;
+        if (start == lo)
+            start++;
+        for ( ; start < hi; start++) {
+            @SuppressWarnings("unchecked")
+            Comparable<Object> pivot = (Comparable) a[start];
+
+            // Set left (and right) to the index where a[start] (pivot) belongs
+            int left = lo;
+            int right = start;
+            assert left <= right;
+            /*
+             * Invariants:
+             *   pivot >= all in [lo, left).
+             *   pivot <  all in [right, start).
+             */
+            while (left < right) {
+                int mid = (left + right) >>> 1;
+                if (pivot.compareTo(a[mid]) < 0)
+                    right = mid;
+                else
+                    left = mid + 1;
+            }
+            assert left == right;
+
+            /*
+             * The invariants still hold: pivot >= all in [lo, left) and
+             * pivot < all in [left, start), so pivot belongs at left.  Note
+             * that if there are elements equal to pivot, left points to the
+             * first slot after them -- that's why this sort is stable.
+             * Slide elements over to make room to make room for pivot.
+             */
+            int n = start - left;  // The number of elements to move
+            // Switch is just an optimization for arraycopy in default case
+            switch(n) {
+                case 2:  a[left + 2] = a[left + 1];
+                case 1:  a[left + 1] = a[left];
+                         break;
+                default: System.arraycopy(a, left, a, left + 1, n);
+            }
+            a[left] = pivot;
+        }
+    }
+
+    /**
+     * Returns the length of the run beginning at the specified position in
+     * the specified array and reverses the run if it is descending (ensuring
+     * that the run will always be ascending when the method returns).
+     *
+     * A run is the longest ascending sequence with:
+     *
+     *    a[lo] <= a[lo + 1] <= a[lo + 2] <= ...
+     *
+     * or the longest descending sequence with:
+     *
+     *    a[lo] >  a[lo + 1] >  a[lo + 2] >  ...
+     *
+     * For its intended use in a stable mergesort, the strictness of the
+     * definition of "descending" is needed so that the call can safely
+     * reverse a descending sequence without violating stability.
+     *
+     * @param a the array in which a run is to be counted and possibly reversed
+     * @param lo index of the first element in the run
+     * @param hi index after the last element that may be contained in the run.
+              It is required that @code{lo < hi}.
+     * @return  the length of the run beginning at the specified position in
+     *          the specified array
+     */
+    @SuppressWarnings("unchecked")
+    private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
+        assert lo < hi;
+        int runHi = lo + 1;
+        if (runHi == hi)
+            return 1;
+
+        // Find end of run, and reverse range if descending
+        if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending
+            while(runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
+                runHi++;
+            reverseRange(a, lo, runHi);
+        } else {                              // Ascending
+            while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
+                runHi++;
+        }
+
+        return runHi - lo;
+    }
+
+    /**
+     * Reverse the specified range of the specified array.
+     *
+     * @param a the array in which a range is to be reversed
+     * @param lo the index of the first element in the range to be reversed
+     * @param hi the index after the last element in the range to be reversed
+     */
+    private static void reverseRange(Object[] a, int lo, int hi) {
+        hi--;
+        while (lo < hi) {
+            Object t = a[lo];
+            a[lo++] = a[hi];
+            a[hi--] = t;
+        }
+    }
+
+    /**
+     * Returns the minimum acceptable run length for an array of the specified
+     * length. Natural runs shorter than this will be extended with
+     * {@link #binarySort}.
+     *
+     * Roughly speaking, the computation is:
+     *
+     *  If n < MIN_MERGE, return n (it's too small to bother with fancy stuff).
+     *  Else if n is an exact power of 2, return MIN_MERGE/2.
+     *  Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k
+     *   is close to, but strictly less than, an exact power of 2.
+     *
+     * For the rationale, see listsort.txt.
+     *
+     * @param n the length of the array to be sorted
+     * @return the length of the minimum run to be merged
+     */
+    private static int minRunLength(int n) {
+        assert n >= 0;
+        int r = 0;      // Becomes 1 if any 1 bits are shifted off
+        while (n >= MIN_MERGE) {
+            r |= (n & 1);
+            n >>= 1;
+        }
+        return n + r;
+    }
+
+    /**
+     * Pushes the specified run onto the pending-run stack.
+     *
+     * @param runBase index of the first element in the run
+     * @param runLen  the number of elements in the run
+     */
+    private void pushRun(int runBase, int runLen) {
+        this.runBase[stackSize] = runBase;
+        this.runLen[stackSize] = runLen;
+        stackSize++;
+    }
+
+    /**
+     * Examines the stack of runs waiting to be merged and merges adjacent runs
+     * until the stack invariants are reestablished:
+     *
+     *     1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
+     *     2. runLen[i - 2] > runLen[i - 1]
+     *
+     * This method is called each time a new run is pushed onto the stack,
+     * so the invariants are guaranteed to hold for i < stackSize upon
+     * entry to the method.
+     */
+    private void mergeCollapse() {
+        while (stackSize > 1) {
+            int n = stackSize - 2;
+            if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
+                if (runLen[n - 1] < runLen[n + 1])
+                    n--;
+                mergeAt(n);
+            } else if (runLen[n] <= runLen[n + 1]) {
+                mergeAt(n);
+            } else {
+                break; // Invariant is established
+            }
+        }
+    }
+
+    /**
+     * Merges all runs on the stack until only one remains.  This method is
+     * called once, to complete the sort.
+     */
+    private void mergeForceCollapse() {
+        while (stackSize > 1) {
+            int n = stackSize - 2;
+            if (n > 0 && runLen[n - 1] < runLen[n + 1])
+                n--;
+            mergeAt(n);
+        }
+    }
+
+    /**
+     * Merges the two runs at stack indices i and i+1.  Run i must be
+     * the penultimate or antepenultimate run on the stack.  In other words,
+     * i must be equal to stackSize-2 or stackSize-3.
+     *
+     * @param i stack index of the first of the two runs to merge
+     */
+    @SuppressWarnings("unchecked")
+    private void mergeAt(int i) {
+        assert stackSize >= 2;
+        assert i >= 0;
+        assert i == stackSize - 2 || i == stackSize - 3;
+
+        int base1 = runBase[i];
+        int len1 = runLen[i];
+        int base2 = runBase[i + 1];
+        int len2 = runLen[i + 1];
+        assert len1 > 0 && len2 > 0;
+        assert base1 + len1 == base2;
+
+        /*
+         * Record the length of the combined runs; if i is the 3rd-last
+         * run now, also slide over the last run (which isn't involved
+         * in this merge).  The current run (i+1) goes away in any case.
+         */
+        runLen[i] = len1 + len2;
+        if (i == stackSize - 3) {
+            runBase[i + 1] = runBase[i + 2];
+            runLen[i + 1] = runLen[i + 2];
+        }
+        stackSize--;
+
+        /*
+         * Find where the first element of run2 goes in run1. Prior elements
+         * in run1 can be ignored (because they're already in place).
+         */
+        int k = gallopRight((Comparable<Object>) a[base2], a, base1, len1, 0);
+        assert k >= 0;
+        base1 += k;
+        len1 -= k;
+        if (len1 == 0)
+            return;
+
+        /*
+         * Find where the last element of run1 goes in run2. Subsequent elements
+         * in run2 can be ignored (because they're already in place).
+         */
+        len2 = gallopLeft((Comparable<Object>) a[base1 + len1 - 1], a,
+                base2, len2, len2 - 1);
+        assert len2 >= 0;
+        if (len2 == 0)
+            return;
+
+        // Merge remaining runs, using tmp array with min(len1, len2) elements
+        if (len1 <= len2)
+            mergeLo(base1, len1, base2, len2);
+        else
+            mergeHi(base1, len1, base2, len2);
+    }
+
+    /**
+     * Locates the position at which to insert the specified key into the
+     * specified sorted range; if the range contains an element equal to key,
+     * returns the index of the leftmost equal element.
+     *
+     * @param key the key whose insertion point to search for
+     * @param a the array in which to search
+     * @param base the index of the first element in the range
+     * @param len the length of the range; must be > 0
+     * @param hint the index at which to begin the search, 0 <= hint < n.
+     *     The closer hint is to the result, the faster this method will run.
+     * @return the int k,  0 <= k <= n such that a[b + k - 1] < key <= a[b + k],
+     *    pretending that a[b - 1] is minus infinity and a[b + n] is infinity.
+     *    In other words, key belongs at index b + k; or in other words,
+     *    the first k elements of a should precede key, and the last n - k
+     *    should follow it.
+     */
+    private static int gallopLeft(Comparable<Object> key, Object[] a,
+            int base, int len, int hint) {
+        assert len > 0 && hint >= 0 && hint < len;
+
+        int lastOfs = 0;
+        int ofs = 1;
+        if (key.compareTo(a[base + hint]) > 0) {
+            // Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs]
+            int maxOfs = len - hint;
+            while (ofs < maxOfs && key.compareTo(a[base + hint + ofs]) > 0) {
+                lastOfs = ofs;
+                ofs = (ofs << 1) + 1;
+                if (ofs <= 0)   // int overflow
+                    ofs = maxOfs;
+            }
+            if (ofs > maxOfs)
+                ofs = maxOfs;
+
+            // Make offsets relative to base
+            lastOfs += hint;
+            ofs += hint;
+        } else { // key <= a[base + hint]
+            // Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs]
+            final int maxOfs = hint + 1;
+            while (ofs < maxOfs && key.compareTo(a[base + hint - ofs]) <= 0) {
+                lastOfs = ofs;
+                ofs = (ofs << 1) + 1;
+                if (ofs <= 0)   // int overflow
+                    ofs = maxOfs;
+            }
+            if (ofs > maxOfs)
+                ofs = maxOfs;
+
+            // Make offsets relative to base
+            int tmp = lastOfs;
+            lastOfs = hint - ofs;
+            ofs = hint - tmp;
+        }
+        assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;
+
+        /*
+         * Now a[base+lastOfs] < key <= a[base+ofs], so key belongs somewhere
+         * to the right of lastOfs but no farther right than ofs.  Do a binary
+         * search, with invariant a[base + lastOfs - 1] < key <= a[base + ofs].
+         */
+        lastOfs++;
+        while (lastOfs < ofs) {
+            int m = lastOfs + ((ofs - lastOfs) >>> 1);
+
+            if (key.compareTo(a[base + m]) > 0)
+                lastOfs = m + 1;  // a[base + m] < key
+            else
+                ofs = m;          // key <= a[base + m]
+        }
+        assert lastOfs == ofs;    // so a[base + ofs - 1] < key <= a[base + ofs]
+        return ofs;
+    }
+
+    /**
+     * Like gallopLeft, except that if the range contains an element equal to
+     * key, gallopRight returns the index after the rightmost equal element.
+     *
+     * @param key the key whose insertion point to search for
+     * @param a the array in which to search
+     * @param base the index of the first element in the range
+     * @param len the length of the range; must be > 0
+     * @param hint the index at which to begin the search, 0 <= hint < n.
+     *     The closer hint is to the result, the faster this method will run.
+     * @return the int k,  0 <= k <= n such that a[b + k - 1] <= key < a[b + k]
+     */
+    private static int gallopRight(Comparable<Object> key, Object[] a,
+            int base, int len, int hint) {
+        assert len > 0 && hint >= 0 && hint < len;
+
+        int ofs = 1;
+        int lastOfs = 0;
+        if (key.compareTo(a[base + hint]) < 0) {
+            // Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs]
+            int maxOfs = hint + 1;
+            while (ofs < maxOfs && key.compareTo(a[base + hint - ofs]) < 0) {
+                lastOfs = ofs;
+                ofs = (ofs << 1) + 1;
+                if (ofs <= 0)   // int overflow
+                    ofs = maxOfs;
+            }
+            if (ofs > maxOfs)
+                ofs = maxOfs;
+
+            // Make offsets relative to b
+            int tmp = lastOfs;
+            lastOfs = hint - ofs;
+            ofs = hint - tmp;
+        } else { // a[b + hint] <= key
+            // Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs]
+            int maxOfs = len - hint;
+            while (ofs < maxOfs && key.compareTo(a[base + hint + ofs]) >= 0) {
+                lastOfs = ofs;
+                ofs = (ofs << 1) + 1;
+                if (ofs <= 0)   // int overflow
+                    ofs = maxOfs;
+            }
+            if (ofs > maxOfs)
+                ofs = maxOfs;
+
+            // Make offsets relative to b
+            lastOfs += hint;
+            ofs += hint;
+        }
+        assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;
+
+        /*
+         * Now a[b + lastOfs] <= key < a[b + ofs], so key belongs somewhere to
+         * the right of lastOfs but no farther right than ofs.  Do a binary
+         * search, with invariant a[b + lastOfs - 1] <= key < a[b + ofs].
+         */
+        lastOfs++;
+        while (lastOfs < ofs) {
+            int m = lastOfs + ((ofs - lastOfs) >>> 1);
+
+            if (key.compareTo(a[base + m]) < 0)
+                ofs = m;          // key < a[b + m]
+            else
+                lastOfs = m + 1;  // a[b + m] <= key
+        }
+        assert lastOfs == ofs;    // so a[b + ofs - 1] <= key < a[b + ofs]
+        return ofs;
+    }
+
+    /**
+     * Merges two adjacent runs in place, in a stable fashion.  The first
+     * element of the first run must be greater than the first element of the
+     * second run (a[base1] > a[base2]), and the last element of the first run
+     * (a[base1 + len1-1]) must be greater than all elements of the second run.
+     *
+     * For performance, this method should be called only when len1 <= len2;
+     * its twin, mergeHi should be called if len1 >= len2.  (Either method
+     * may be called if len1 == len2.)
+     *
+     * @param base1 index of first element in first run to be merged
+     * @param len1  length of first run to be merged (must be > 0)
+     * @param base2 index of first element in second run to be merged
+     *        (must be aBase + aLen)
+     * @param len2  length of second run to be merged (must be > 0)
+     */
+    @SuppressWarnings("unchecked")
+    private void mergeLo(int base1, int len1, int base2, int len2) {
+        assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
+
+        // Copy first run into temp array
+        Object[] a = this.a; // For performance
+        Object[] tmp = ensureCapacity(len1);
+        System.arraycopy(a, base1, tmp, 0, len1);
+
+        int cursor1 = 0;       // Indexes into tmp array
+        int cursor2 = base2;   // Indexes int a
+        int dest = base1;      // Indexes int a
+
+        // Move first element of second run and deal with degenerate cases
+        a[dest++] = a[cursor2++];
+        if (--len2 == 0) {
+            System.arraycopy(tmp, cursor1, a, dest, len1);
+            return;
+        }
+        if (len1 == 1) {
+            System.arraycopy(a, cursor2, a, dest, len2);
+            a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
+            return;
+        }
+
+        int minGallop = this.minGallop;  // Use local variable for performance
+    outer:
+        while (true) {
+            int count1 = 0; // Number of times in a row that first run won
+            int count2 = 0; // Number of times in a row that second run won
+
+            /*
+             * Do the straightforward thing until (if ever) one run starts
+             * winning consistently.
+             */
+            do {
+                assert len1 > 1 && len2 > 0;
+                if (((Comparable) a[cursor2]).compareTo(tmp[cursor1]) < 0) {
+                    a[dest++] = a[cursor2++];
+                    count2++;
+                    count1 = 0;
+                    if (--len2 == 0)
+                        break outer;
+                } else {
+                    a[dest++] = tmp[cursor1++];
+                    count1++;
+                    count2 = 0;
+                    if (--len1 == 1)
+                        break outer;
+                }
+            } while ((count1 | count2) < minGallop);
+
+            /*
+             * One run is winning so consistently that galloping may be a
+             * huge win. So try that, and continue galloping until (if ever)
+             * neither run appears to be winning consistently anymore.
+             */
+            do {
+                assert len1 > 1 && len2 > 0;
+                count1 = gallopRight((Comparable) a[cursor2], tmp, cursor1, len1, 0);
+                if (count1 != 0) {
+                    System.arraycopy(tmp, cursor1, a, dest, count1);
+                    dest += count1;
+                    cursor1 += count1;
+                    len1 -= count1;
+                    if (len1 <= 1)  // len1 == 1 || len1 == 0
+                        break outer;
+                }
+                a[dest++] = a[cursor2++];
+                if (--len2 == 0)
+                    break outer;
+
+                count2 = gallopLeft((Comparable) tmp[cursor1], a, cursor2, len2, 0);
+                if (count2 != 0) {
+                    System.arraycopy(a, cursor2, a, dest, count2);
+                    dest += count2;
+                    cursor2 += count2;
+                    len2 -= count2;
+                    if (len2 == 0)
+                        break outer;
+                }
+                a[dest++] = tmp[cursor1++];
+                if (--len1 == 1)
+                    break outer;
+                minGallop--;
+            } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
+            if (minGallop < 0)
+                minGallop = 0;
+            minGallop += 2;  // Penalize for leaving gallop mode
+        }  // End of "outer" loop
+        this.minGallop = minGallop < 1 ? 1 : minGallop;  // Write back to field
+
+        if (len1 == 1) {
+            assert len2 > 0;
+            System.arraycopy(a, cursor2, a, dest, len2);
+            a[dest + len2] = tmp[cursor1]; //  Last elt of run 1 to end of merge
+        } else if (len1 == 0) {
+            throw new IllegalArgumentException(
+                "Comparison method violates its general contract!");
+        } else {
+            assert len2 == 0;
+            assert len1 > 1;
+            System.arraycopy(tmp, cursor1, a, dest, len1);
+        }
+    }
+
+    /**
+     * Like mergeLo, except that this method should be called only if
+     * len1 >= len2; mergeLo should be called if len1 <= len2.  (Either method
+     * may be called if len1 == len2.)
+     *
+     * @param base1 index of first element in first run to be merged
+     * @param len1  length of first run to be merged (must be > 0)
+     * @param base2 index of first element in second run to be merged
+     *        (must be aBase + aLen)
+     * @param len2  length of second run to be merged (must be > 0)
+     */
+    @SuppressWarnings("unchecked")
+    private void mergeHi(int base1, int len1, int base2, int len2) {
+        assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
+
+        // Copy second run into temp array
+        Object[] a = this.a; // For performance
+        Object[] tmp = ensureCapacity(len2);
+        System.arraycopy(a, base2, tmp, 0, len2);
+
+        int cursor1 = base1 + len1 - 1;  // Indexes into a
+        int cursor2 = len2 - 1;          // Indexes into tmp array
+        int dest = base2 + len2 - 1;     // Indexes into a
+
+        // Move last element of first run and deal with degenerate cases
+        a[dest--] = a[cursor1--];
+        if (--len1 == 0) {
+            System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2);
+            return;
+        }
+        if (len2 == 1) {
+            dest -= len1;
+            cursor1 -= len1;
+            System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
+            a[dest] = tmp[cursor2];
+            return;
+        }
+
+        int minGallop = this.minGallop;  // Use local variable for performance
+    outer:
+        while (true) {
+            int count1 = 0; // Number of times in a row that first run won
+            int count2 = 0; // Number of times in a row that second run won
+
+            /*
+             * Do the straightforward thing until (if ever) one run
+             * appears to win consistently.
+             */
+            do {
+                assert len1 > 0 && len2 > 1;
+                if (((Comparable) tmp[cursor2]).compareTo(a[cursor1]) < 0) {
+                    a[dest--] = a[cursor1--];
+                    count1++;
+                    count2 = 0;
+                    if (--len1 == 0)
+                        break outer;
+                } else {
+                    a[dest--] = tmp[cursor2--];
+                    count2++;
+                    count1 = 0;
+                    if (--len2 == 1)
+                        break outer;
+                }
+            } while ((count1 | count2) < minGallop);
+
+            /*
+             * One run is winning so consistently that galloping may be a
+             * huge win. So try that, and continue galloping until (if ever)
+             * neither run appears to be winning consistently anymore.
+             */
+            do {
+                assert len1 > 0 && len2 > 1;
+                count1 = len1 - gallopRight((Comparable) tmp[cursor2], a, base1, len1, len1 - 1);
+                if (count1 != 0) {
+                    dest -= count1;
+                    cursor1 -= count1;
+                    len1 -= count1;
+                    System.arraycopy(a, cursor1 + 1, a, dest + 1, count1);
+                    if (len1 == 0)
+                        break outer;
+                }
+                a[dest--] = tmp[cursor2--];
+                if (--len2 == 1)
+                    break outer;
+
+                count2 = len2 - gallopLeft((Comparable) a[cursor1], tmp, 0, len2, len2 - 1);
+                if (count2 != 0) {
+                    dest -= count2;
+                    cursor2 -= count2;
+                    len2 -= count2;
+                    System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2);
+                    if (len2 <= 1)
+                        break outer; // len2 == 1 || len2 == 0
+                }
+                a[dest--] = a[cursor1--];
+                if (--len1 == 0)
+                    break outer;
+                minGallop--;
+            } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
+            if (minGallop < 0)
+                minGallop = 0;
+            minGallop += 2;  // Penalize for leaving gallop mode
+        }  // End of "outer" loop
+        this.minGallop = minGallop < 1 ? 1 : minGallop;  // Write back to field
+
+        if (len2 == 1) {
+            assert len1 > 0;
+            dest -= len1;
+            cursor1 -= len1;
+            System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
+            a[dest] = tmp[cursor2];  // Move first elt of run2 to front of merge
+        } else if (len2 == 0) {
+            throw new IllegalArgumentException(
+                "Comparison method violates its general contract!");
+        } else {
+            assert len1 == 0;
+            assert len2 > 0;
+            System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2);
+        }
+    }
+
+    /**
+     * Ensures that the external array tmp has at least the specified
+     * number of elements, increasing its size if necessary.  The size
+     * increases exponentially to ensure amortized linear time complexity.
+     *
+     * @param minCapacity the minimum required capacity of the tmp array
+     * @return tmp, whether or not it grew
+     */
+    private Object[]  ensureCapacity(int minCapacity) {
+        if (tmp.length < minCapacity) {
+            // Compute smallest power of 2 > minCapacity
+            int newSize = minCapacity;
+            newSize |= newSize >> 1;
+            newSize |= newSize >> 2;
+            newSize |= newSize >> 4;
+            newSize |= newSize >> 8;
+            newSize |= newSize >> 16;
+            newSize++;
+
+            if (newSize < 0) // Not bloody likely!
+                newSize = minCapacity;
+            else
+                newSize = Math.min(newSize, a.length >>> 1);
+
+            @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
+            Object[] newArray = new Object[newSize];
+            tmp = newArray;
+        }
+        return tmp;
+    }
+
+    /**
+     * Checks that fromIndex and toIndex are in range, and throws an
+     * appropriate exception if they aren't.
+     *
+     * @param arrayLen the length of the array
+     * @param fromIndex the index of the first element of the range
+     * @param toIndex the index after the last element of the range
+     * @throws IllegalArgumentException if fromIndex > toIndex
+     * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
+     *         or toIndex > arrayLen
+     */
+    private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
+        if (fromIndex > toIndex)
+            throw new IllegalArgumentException("fromIndex(" + fromIndex +
+                       ") > toIndex(" + toIndex+")");
+        if (fromIndex < 0)
+            throw new ArrayIndexOutOfBoundsException(fromIndex);
+        if (toIndex > arrayLen)
+            throw new ArrayIndexOutOfBoundsException(toIndex);
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/classes/java/util/TimSort.java	Wed Jul 29 14:24:19 2009 -0700
@@ -0,0 +1,928 @@
+/*
+ * Copyright 2009 Google Inc.  All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Sun designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Sun in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+
+package java.util;
+
+/**
+ * A stable, adaptive, iterative mergesort that requires far fewer than
+ * n lg(n) comparisons when running on partially sorted arrays, while
+ * offering performance comparable to a traditional mergesort when run
+ * on random arrays.  Like all proper mergesorts, this sort is stable and
+ * runs O(n log n) time (worst case).  In the worst case, this sort requires
+ * temporary storage space for n/2 object references; in the best case,
+ * it requires only a small constant amount of space.
+ *
+ * This implementation was adapted from Tim Peters's list sort for
+ * Python, which is described in detail here:
+ *
+ *   http://svn.python.org/projects/python/trunk/Objects/listsort.txt
+ *
+ * Tim's C code may be found here:
+ *
+ *   http://svn.python.org/projects/python/trunk/Objects/listobject.c
+ *
+ * The underlying techniques are described in this paper (and may have
+ * even earlier origins):
+ *
+ *  "Optimistic Sorting and Information Theoretic Complexity"
+ *  Peter McIlroy
+ *  SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms),
+ *  pp 467-474, Austin, Texas, 25-27 January 1993.
+ *
+ * While the API to this class consists solely of static methods, it is
+ * (privately) instantiable; a TimSort instance holds the state of an ongoing
+ * sort, assuming the input array is large enough to warrant the full-blown
+ * TimSort. Small arrays are sorted in place, using a binary insertion sort.
+ *
+ * @author Josh Bloch
+ */
+class TimSort<T> {
+    /**
+     * This is the minimum sized sequence that will be merged.  Shorter
+     * sequences will be lengthened by calling binarySort.  If the entire
+     * array is less than this length, no merges will be performed.
+     *
+     * This constant should be a power of two.  It was 64 in Tim Peter's C
+     * implementation, but 32 was empirically determined to work better in
+     * this implementation.  In the unlikely event that you set this constant
+     * to be a number that's not a power of two, you'll need to change the
+     * {@link #minRunLength} computation.
+     *
+     * If you decrease this constant, you must change the stackLen
+     * computation in the TimSort constructor, or you risk an
+     * ArrayOutOfBounds exception.  See listsort.txt for a discussion
+     * of the minimum stack length required as a function of the length
+     * of the array being sorted and the minimum merge sequence length.
+     */
+    private static final int MIN_MERGE = 32;
+
+    /**
+     * The array being sorted.
+     */
+    private final T[] a;
+
+    /**
+     * The comparator for this sort.
+     */
+    private final Comparator<? super T> c;
+
+    /**
+     * When we get into galloping mode, we stay there until both runs win less
+     * often than MIN_GALLOP consecutive times.
+     */
+    private static final int  MIN_GALLOP = 7;
+
+    /**
+     * This controls when we get *into* galloping mode.  It is initialized
+     * to MIN_GALLOP.  The mergeLo and mergeHi methods nudge it higher for
+     * random data, and lower for highly structured data.
+     */
+    private int minGallop = MIN_GALLOP;
+
+    /**
+     * Maximum initial size of tmp array, which is used for merging.  The array
+     * can grow to accommodate demand.
+     *
+     * Unlike Tim's original C version, we do not allocate this much storage
+     * when sorting smaller arrays.  This change was required for performance.
+     */
+    private static final int INITIAL_TMP_STORAGE_LENGTH = 256;
+
+    /**
+     * Temp storage for merges.
+     */
+    private T[] tmp; // Actual runtime type will be Object[], regardless of T
+
+    /**
+     * A stack of pending runs yet to be merged.  Run i starts at
+     * address base[i] and extends for len[i] elements.  It's always
+     * true (so long as the indices are in bounds) that:
+     *
+     *     runBase[i] + runLen[i] == runBase[i + 1]
+     *
+     * so we could cut the storage for this, but it's a minor amount,
+     * and keeping all the info explicit simplifies the code.
+     */
+    private int stackSize = 0;  // Number of pending runs on stack
+    private final int[] runBase;
+    private final int[] runLen;
+
+    /**
+     * Creates a TimSort instance to maintain the state of an ongoing sort.
+     *
+     * @param a the array to be sorted
+     * @param c the comparator to determine the order of the sort
+     */
+    private TimSort(T[] a, Comparator<? super T> c) {
+        this.a = a;
+        this.c = c;
+
+        // Allocate temp storage (which may be increased later if necessary)
+        int len = a.length;
+        @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
+        T[] newArray = (T[]) new Object[len < 2 * INITIAL_TMP_STORAGE_LENGTH ?
+                                        len >>> 1 : INITIAL_TMP_STORAGE_LENGTH];
+        tmp = newArray;
+
+        /*
+         * Allocate runs-to-be-merged stack (which cannot be expanded).  The
+         * stack length requirements are described in listsort.txt.  The C
+         * version always uses the same stack length (85), but this was
+         * measured to be too expensive when sorting "mid-sized" arrays (e.g.,
+         * 100 elements) in Java.  Therefore, we use smaller (but sufficiently
+         * large) stack lengths for smaller arrays.  The "magic numbers" in the
+         * computation below must be changed if MIN_MERGE is decreased.  See
+         * the MIN_MERGE declaration above for more information.
+         */
+        int stackLen = (len <    120  ?  5 :
+                        len <   1542  ? 10 :
+                        len < 119151  ? 19 : 40);
+        runBase = new int[stackLen];
+        runLen = new int[stackLen];
+    }
+
+    /*
+     * The next two methods (which are package private and static) constitute
+     * the entire API of this class.  Each of these methods obeys the contract
+     * of the public method with the same signature in java.util.Arrays.
+     */
+
+    static <T> void sort(T[] a, Comparator<? super T> c) {
+        sort(a, 0, a.length, c);
+    }
+
+    static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c) {
+        if (c == null) {
+            Arrays.sort(a, lo, hi);
+            return;
+        }
+
+        rangeCheck(a.length, lo, hi);
+        int nRemaining  = hi - lo;
+        if (nRemaining < 2)
+            return;  // Arrays of size 0 and 1 are always sorted
+
+        // If array is small, do a "mini-TimSort" with no merges
+        if (nRemaining < MIN_MERGE) {
+            int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
+            binarySort(a, lo, hi, lo + initRunLen, c);
+            return;
+        }
+
+        /**
+         * March over the array once, left to right, finding natural runs,
+         * extending short natural runs to minRun elements, and merging runs
+         * to maintain stack invariant.
+         */
+        TimSort<T> ts = new TimSort<T>(a, c);
+        int minRun = minRunLength(nRemaining);
+        do {
+            // Identify next run
+            int runLen = countRunAndMakeAscending(a, lo, hi, c);
+
+            // If run is short, extend to min(minRun, nRemaining)
+            if (runLen < minRun) {
+                int force = nRemaining <= minRun ? nRemaining : minRun;
+                binarySort(a, lo, lo + force, lo + runLen, c);
+                runLen = force;
+            }
+
+            // Push run onto pending-run stack, and maybe merge
+            ts.pushRun(lo, runLen);
+            ts.mergeCollapse();
+
+            // Advance to find next run
+            lo += runLen;
+            nRemaining -= runLen;
+        } while (nRemaining != 0);
+
+        // Merge all remaining runs to complete sort
+        assert lo == hi;
+        ts.mergeForceCollapse();
+        assert ts.stackSize == 1;
+    }
+
+    /**
+     * Sorts the specified portion of the specified array using a binary
+     * insertion sort.  This is the best method for sorting small numbers
+     * of elements.  It requires O(n log n) compares, but O(n^2) data
+     * movement (worst case).
+     *
+     * If the initial part of the specified range is already sorted,
+     * this method can take advantage of it: the method assumes that the
+     * elements from index {@code lo}, inclusive, to {@code start},
+     * exclusive are already sorted.
+     *
+     * @param a the array in which a range is to be sorted
+     * @param lo the index of the first element in the range to be sorted
+     * @param hi the index after the last element in the range to be sorted
+     * @param start the index of the first element in the range that is
+     *        not already known to be sorted (@code lo <= start <= hi}
+     * @param c comparator to used for the sort
+     */
+    @SuppressWarnings("fallthrough")
+    private static <T> void binarySort(T[] a, int lo, int hi, int start,
+                                       Comparator<? super T> c) {
+        assert lo <= start && start <= hi;
+        if (start == lo)
+            start++;
+        for ( ; start < hi; start++) {
+            T pivot = a[start];
+
+            // Set left (and right) to the index where a[start] (pivot) belongs
+            int left = lo;
+            int right = start;
+            assert left <= right;
+            /*
+             * Invariants:
+             *   pivot >= all in [lo, left).
+             *   pivot <  all in [right, start).
+             */
+            while (left < right) {
+                int mid = (left + right) >>> 1;
+                if (c.compare(pivot, a[mid]) < 0)
+                    right = mid;
+                else
+                    left = mid + 1;
+            }
+            assert left == right;
+
+            /*
+             * The invariants still hold: pivot >= all in [lo, left) and
+             * pivot < all in [left, start), so pivot belongs at left.  Note
+             * that if there are elements equal to pivot, left points to the
+             * first slot after them -- that's why this sort is stable.
+             * Slide elements over to make room to make room for pivot.
+             */
+            int n = start - left;  // The number of elements to move
+            // Switch is just an optimization for arraycopy in default case
+            switch(n) {
+                case 2:  a[left + 2] = a[left + 1];
+                case 1:  a[left + 1] = a[left];
+                         break;
+                default: System.arraycopy(a, left, a, left + 1, n);
+            }
+            a[left] = pivot;
+        }
+    }
+
+    /**
+     * Returns the length of the run beginning at the specified position in
+     * the specified array and reverses the run if it is descending (ensuring
+     * that the run will always be ascending when the method returns).
+     *
+     * A run is the longest ascending sequence with:
+     *
+     *    a[lo] <= a[lo + 1] <= a[lo + 2] <= ...
+     *
+     * or the longest descending sequence with:
+     *
+     *    a[lo] >  a[lo + 1] >  a[lo + 2] >  ...
+     *
+     * For its intended use in a stable mergesort, the strictness of the
+     * definition of "descending" is needed so that the call can safely
+     * reverse a descending sequence without violating stability.
+     *
+     * @param a the array in which a run is to be counted and possibly reversed
+     * @param lo index of the first element in the run
+     * @param hi index after the last element that may be contained in the run.
+              It is required that @code{lo < hi}.
+     * @param c the comparator to used for the sort
+     * @return  the length of the run beginning at the specified position in
+     *          the specified array
+     */
+    private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
+                                                    Comparator<? super T> c) {
+        assert lo < hi;
+        int runHi = lo + 1;
+        if (runHi == hi)
+            return 1;
+
+        // Find end of run, and reverse range if descending
+        if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
+            while(runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
+                runHi++;
+            reverseRange(a, lo, runHi);
+        } else {                              // Ascending
+            while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
+                runHi++;
+        }
+
+        return runHi - lo;
+    }
+
+    /**
+     * Reverse the specified range of the specified array.
+     *
+     * @param a the array in which a range is to be reversed
+     * @param lo the index of the first element in the range to be reversed
+     * @param hi the index after the last element in the range to be reversed
+     */
+    private static void reverseRange(Object[] a, int lo, int hi) {
+        hi--;
+        while (lo < hi) {
+            Object t = a[lo];
+            a[lo++] = a[hi];
+            a[hi--] = t;
+        }
+    }
+
+    /**
+     * Returns the minimum acceptable run length for an array of the specified
+     * length. Natural runs shorter than this will be extended with
+     * {@link #binarySort}.
+     *
+     * Roughly speaking, the computation is:
+     *
+     *  If n < MIN_MERGE, return n (it's too small to bother with fancy stuff).
+     *  Else if n is an exact power of 2, return MIN_MERGE/2.
+     *  Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k
+     *   is close to, but strictly less than, an exact power of 2.
+     *
+     * For the rationale, see listsort.txt.
+     *
+     * @param n the length of the array to be sorted
+     * @return the length of the minimum run to be merged
+     */
+    private static int minRunLength(int n) {
+        assert n >= 0;
+        int r = 0;      // Becomes 1 if any 1 bits are shifted off
+        while (n >= MIN_MERGE) {
+            r |= (n & 1);
+            n >>= 1;
+        }
+        return n + r;
+    }
+
+    /**
+     * Pushes the specified run onto the pending-run stack.
+     *
+     * @param runBase index of the first element in the run
+     * @param runLen  the number of elements in the run
+     */
+    private void pushRun(int runBase, int runLen) {
+        this.runBase[stackSize] = runBase;
+        this.runLen[stackSize] = runLen;
+        stackSize++;
+    }
+
+    /**
+     * Examines the stack of runs waiting to be merged and merges adjacent runs
+     * until the stack invariants are reestablished:
+     *
+     *     1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
+     *     2. runLen[i - 2] > runLen[i - 1]
+     *
+     * This method is called each time a new run is pushed onto the stack,
+     * so the invariants are guaranteed to hold for i < stackSize upon
+     * entry to the method.
+     */
+    private void mergeCollapse() {
+        while (stackSize > 1) {
+            int n = stackSize - 2;
+            if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
+                if (runLen[n - 1] < runLen[n + 1])
+                    n--;
+                mergeAt(n);
+            } else if (runLen[n] <= runLen[n + 1]) {
+                mergeAt(n);
+            } else {
+                break; // Invariant is established
+            }
+        }
+    }
+
+    /**
+     * Merges all runs on the stack until only one remains.  This method is
+     * called once, to complete the sort.
+     */
+    private void mergeForceCollapse() {
+        while (stackSize > 1) {
+            int n = stackSize - 2;
+            if (n > 0 && runLen[n - 1] < runLen[n + 1])
+                n--;
+            mergeAt(n);
+        }
+    }
+
+    /**
+     * Merges the two runs at stack indices i and i+1.  Run i must be
+     * the penultimate or antepenultimate run on the stack.  In other words,
+     * i must be equal to stackSize-2 or stackSize-3.
+     *
+     * @param i stack index of the first of the two runs to merge
+     */
+    private void mergeAt(int i) {
+        assert stackSize >= 2;
+        assert i >= 0;
+        assert i == stackSize - 2 || i == stackSize - 3;
+
+        int base1 = runBase[i];
+        int len1 = runLen[i];
+        int base2 = runBase[i + 1];
+        int len2 = runLen[i + 1];
+        assert len1 > 0 && len2 > 0;
+        assert base1 + len1 == base2;
+
+        /*
+         * Record the length of the combined runs; if i is the 3rd-last
+         * run now, also slide over the last run (which isn't involved
+         * in this merge).  The current run (i+1) goes away in any case.
+         */
+        runLen[i] = len1 + len2;
+        if (i == stackSize - 3) {
+            runBase[i + 1] = runBase[i + 2];
+            runLen[i + 1] = runLen[i + 2];
+        }
+        stackSize--;
+
+        /*
+         * Find where the first element of run2 goes in run1. Prior elements
+         * in run1 can be ignored (because they're already in place).
+         */
+        int k = gallopRight(a[base2], a, base1, len1, 0, c);
+        assert k >= 0;
+        base1 += k;
+        len1 -= k;
+        if (len1 == 0)
+            return;
+
+        /*
+         * Find where the last element of run1 goes in run2. Subsequent elements
+         * in run2 can be ignored (because they're already in place).
+         */
+        len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);
+        assert len2 >= 0;
+        if (len2 == 0)
+            return;
+
+        // Merge remaining runs, using tmp array with min(len1, len2) elements
+        if (len1 <= len2)
+            mergeLo(base1, len1, base2, len2);
+        else
+            mergeHi(base1, len1, base2, len2);
+    }
+
+    /**
+     * Locates the position at which to insert the specified key into the
+     * specified sorted range; if the range contains an element equal to key,
+     * returns the index of the leftmost equal element.
+     *
+     * @param key the key whose insertion point to search for
+     * @param a the array in which to search
+     * @param base the index of the first element in the range
+     * @param len the length of the range; must be > 0
+     * @param hint the index at which to begin the search, 0 <= hint < n.
+     *     The closer hint is to the result, the faster this method will run.
+     * @param c the comparator used to order the range, and to search
+     * @return the int k,  0 <= k <= n such that a[b + k - 1] < key <= a[b + k],
+     *    pretending that a[b - 1] is minus infinity and a[b + n] is infinity.
+     *    In other words, key belongs at index b + k; or in other words,
+     *    the first k elements of a should precede key, and the last n - k
+     *    should follow it.
+     */
+    private static <T> int gallopLeft(T key, T[] a, int base, int len, int hint,
+                                      Comparator<? super T> c) {
+        assert len > 0 && hint >= 0 && hint < len;
+        int lastOfs = 0;
+        int ofs = 1;
+        if (c.compare(key, a[base + hint]) > 0) {
+            // Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs]
+            int maxOfs = len - hint;
+            while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) > 0) {
+                lastOfs = ofs;
+                ofs = (ofs << 1) + 1;
+                if (ofs <= 0)   // int overflow
+                    ofs = maxOfs;
+            }
+            if (ofs > maxOfs)
+                ofs = maxOfs;
+
+            // Make offsets relative to base
+            lastOfs += hint;
+            ofs += hint;
+        } else { // key <= a[base + hint]
+            // Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs]
+            final int maxOfs = hint + 1;
+            while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) <= 0) {
+                lastOfs = ofs;
+                ofs = (ofs << 1) + 1;
+                if (ofs <= 0)   // int overflow
+                    ofs = maxOfs;
+            }
+            if (ofs > maxOfs)
+                ofs = maxOfs;
+
+            // Make offsets relative to base
+            int tmp = lastOfs;
+            lastOfs = hint - ofs;
+            ofs = hint - tmp;
+        }
+        assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;
+
+        /*
+         * Now a[base+lastOfs] < key <= a[base+ofs], so key belongs somewhere
+         * to the right of lastOfs but no farther right than ofs.  Do a binary
+         * search, with invariant a[base + lastOfs - 1] < key <= a[base + ofs].
+         */
+        lastOfs++;
+        while (lastOfs < ofs) {
+            int m = lastOfs + ((ofs - lastOfs) >>> 1);
+
+            if (c.compare(key, a[base + m]) > 0)
+                lastOfs = m + 1;  // a[base + m] < key
+            else
+                ofs = m;          // key <= a[base + m]
+        }
+        assert lastOfs == ofs;    // so a[base + ofs - 1] < key <= a[base + ofs]
+        return ofs;
+    }
+
+    /**
+     * Like gallopLeft, except that if the range contains an element equal to
+     * key, gallopRight returns the index after the rightmost equal element.
+     *
+     * @param key the key whose insertion point to search for
+     * @param a the array in which to search
+     * @param base the index of the first element in the range
+     * @param len the length of the range; must be > 0
+     * @param hint the index at which to begin the search, 0 <= hint < n.
+     *     The closer hint is to the result, the faster this method will run.
+     * @param c the comparator used to order the range, and to search
+     * @return the int k,  0 <= k <= n such that a[b + k - 1] <= key < a[b + k]
+     */
+    private static <T> int gallopRight(T key, T[] a, int base, int len,
+                                       int hint, Comparator<? super T> c) {
+        assert len > 0 && hint >= 0 && hint < len;
+
+        int ofs = 1;
+        int lastOfs = 0;
+        if (c.compare(key, a[base + hint]) < 0) {
+            // Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs]
+            int maxOfs = hint + 1;
+            while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) < 0) {
+                lastOfs = ofs;
+                ofs = (ofs << 1) + 1;
+                if (ofs <= 0)   // int overflow
+                    ofs = maxOfs;
+            }
+            if (ofs > maxOfs)
+                ofs = maxOfs;
+
+            // Make offsets relative to b
+            int tmp = lastOfs;
+            lastOfs = hint - ofs;
+            ofs = hint - tmp;
+        } else { // a[b + hint] <= key
+            // Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs]
+            int maxOfs = len - hint;
+            while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) >= 0) {
+                lastOfs = ofs;
+                ofs = (ofs << 1) + 1;
+                if (ofs <= 0)   // int overflow
+                    ofs = maxOfs;
+            }
+            if (ofs > maxOfs)
+                ofs = maxOfs;
+
+            // Make offsets relative to b
+            lastOfs += hint;
+            ofs += hint;
+        }
+        assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;
+
+        /*
+         * Now a[b + lastOfs] <= key < a[b + ofs], so key belongs somewhere to
+         * the right of lastOfs but no farther right than ofs.  Do a binary
+         * search, with invariant a[b + lastOfs - 1] <= key < a[b + ofs].
+         */
+        lastOfs++;
+        while (lastOfs < ofs) {
+            int m = lastOfs + ((ofs - lastOfs) >>> 1);
+
+            if (c.compare(key, a[base + m]) < 0)
+                ofs = m;          // key < a[b + m]
+            else
+                lastOfs = m + 1;  // a[b + m] <= key
+        }
+        assert lastOfs == ofs;    // so a[b + ofs - 1] <= key < a[b + ofs]
+        return ofs;
+    }
+
+    /**
+     * Merges two adjacent runs in place, in a stable fashion.  The first
+     * element of the first run must be greater than the first element of the
+     * second run (a[base1] > a[base2]), and the last element of the first run
+     * (a[base1 + len1-1]) must be greater than all elements of the second run.
+     *
+     * For performance, this method should be called only when len1 <= len2;
+     * its twin, mergeHi should be called if len1 >= len2.  (Either method
+     * may be called if len1 == len2.)
+     *
+     * @param base1 index of first element in first run to be merged
+     * @param len1  length of first run to be merged (must be > 0)
+     * @param base2 index of first element in second run to be merged
+     *        (must be aBase + aLen)
+     * @param len2  length of second run to be merged (must be > 0)
+     */
+    private void mergeLo(int base1, int len1, int base2, int len2) {
+        assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
+
+        // Copy first run into temp array
+        T[] a = this.a; // For performance
+        T[] tmp = ensureCapacity(len1);
+        System.arraycopy(a, base1, tmp, 0, len1);
+
+        int cursor1 = 0;       // Indexes into tmp array
+        int cursor2 = base2;   // Indexes int a
+        int dest = base1;      // Indexes int a
+
+        // Move first element of second run and deal with degenerate cases
+        a[dest++] = a[cursor2++];
+        if (--len2 == 0) {
+            System.arraycopy(tmp, cursor1, a, dest, len1);
+            return;
+        }
+        if (len1 == 1) {
+            System.arraycopy(a, cursor2, a, dest, len2);
+            a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
+            return;
+        }
+
+        Comparator<? super T> c = this.c;  // Use local variable for performance
+        int minGallop = this.minGallop;    //  "    "       "     "      "
+    outer:
+        while (true) {
+            int count1 = 0; // Number of times in a row that first run won
+            int count2 = 0; // Number of times in a row that second run won
+
+            /*
+             * Do the straightforward thing until (if ever) one run starts
+             * winning consistently.
+             */
+            do {
+                assert len1 > 1 && len2 > 0;
+                if (c.compare(a[cursor2], tmp[cursor1]) < 0) {
+                    a[dest++] = a[cursor2++];
+                    count2++;
+                    count1 = 0;
+                    if (--len2 == 0)
+                        break outer;
+                } else {
+                    a[dest++] = tmp[cursor1++];
+                    count1++;
+                    count2 = 0;
+                    if (--len1 == 1)
+                        break outer;
+                }
+            } while ((count1 | count2) < minGallop);
+
+            /*
+             * One run is winning so consistently that galloping may be a
+             * huge win. So try that, and continue galloping until (if ever)
+             * neither run appears to be winning consistently anymore.
+             */
+            do {
+                assert len1 > 1 && len2 > 0;
+                count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0, c);
+                if (count1 != 0) {
+                    System.arraycopy(tmp, cursor1, a, dest, count1);
+                    dest += count1;
+                    cursor1 += count1;
+                    len1 -= count1;
+                    if (len1 <= 1) // len1 == 1 || len1 == 0
+                        break outer;
+                }
+                a[dest++] = a[cursor2++];
+                if (--len2 == 0)
+                    break outer;
+
+                count2 = gallopLeft(tmp[cursor1], a, cursor2, len2, 0, c);
+                if (count2 != 0) {
+                    System.arraycopy(a, cursor2, a, dest, count2);
+                    dest += count2;
+                    cursor2 += count2;
+                    len2 -= count2;
+                    if (len2 == 0)
+                        break outer;
+                }
+                a[dest++] = tmp[cursor1++];
+                if (--len1 == 1)
+                    break outer;
+                minGallop--;
+            } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
+            if (minGallop < 0)
+                minGallop = 0;
+            minGallop += 2;  // Penalize for leaving gallop mode
+        }  // End of "outer" loop
+        this.minGallop = minGallop < 1 ? 1 : minGallop;  // Write back to field
+
+        if (len1 == 1) {
+            assert len2 > 0;
+            System.arraycopy(a, cursor2, a, dest, len2);
+            a[dest + len2] = tmp[cursor1]; //  Last elt of run 1 to end of merge
+        } else if (len1 == 0) {
+            throw new IllegalArgumentException(
+                "Comparison method violates its general contract!");
+        } else {
+            assert len2 == 0;
+            assert len1 > 1;
+            System.arraycopy(tmp, cursor1, a, dest, len1);
+        }
+    }
+
+    /**
+     * Like mergeLo, except that this method should be called only if
+     * len1 >= len2; mergeLo should be called if len1 <= len2.  (Either method
+     * may be called if len1 == len2.)
+     *
+     * @param base1 index of first element in first run to be merged
+     * @param len1  length of first run to be merged (must be > 0)
+     * @param base2 index of first element in second run to be merged
+     *        (must be aBase + aLen)
+     * @param len2  length of second run to be merged (must be > 0)
+     */
+    private void mergeHi(int base1, int len1, int base2, int len2) {
+        assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
+
+        // Copy second run into temp array
+        T[] a = this.a; // For performance
+        T[] tmp = ensureCapacity(len2);
+        System.arraycopy(a, base2, tmp, 0, len2);
+
+        int cursor1 = base1 + len1 - 1;  // Indexes into a
+        int cursor2 = len2 - 1;          // Indexes into tmp array
+        int dest = base2 + len2 - 1;     // Indexes into a
+
+        // Move last element of first run and deal with degenerate cases
+        a[dest--] = a[cursor1--];
+        if (--len1 == 0) {
+            System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2);
+            return;
+        }
+        if (len2 == 1) {
+            dest -= len1;
+            cursor1 -= len1;
+            System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
+            a[dest] = tmp[cursor2];
+            return;
+        }
+
+        Comparator<? super T> c = this.c;  // Use local variable for performance
+        int minGallop = this.minGallop;    //  "    "       "     "      "
+    outer:
+        while (true) {
+            int count1 = 0; // Number of times in a row that first run won
+            int count2 = 0; // Number of times in a row that second run won
+
+            /*
+             * Do the straightforward thing until (if ever) one run
+             * appears to win consistently.
+             */
+            do {
+                assert len1 > 0 && len2 > 1;
+                if (c.compare(tmp[cursor2], a[cursor1]) < 0) {
+                    a[dest--] = a[cursor1--];
+                    count1++;
+                    count2 = 0;
+                    if (--len1 == 0)
+                        break outer;
+                } else {
+                    a[dest--] = tmp[cursor2--];
+                    count2++;
+                    count1 = 0;
+                    if (--len2 == 1)
+                        break outer;
+                }
+            } while ((count1 | count2) < minGallop);
+
+            /*
+             * One run is winning so consistently that galloping may be a
+             * huge win. So try that, and continue galloping until (if ever)
+             * neither run appears to be winning consistently anymore.
+             */
+            do {
+                assert len1 > 0 && len2 > 1;
+                count1 = len1 - gallopRight(tmp[cursor2], a, base1, len1, len1 - 1, c);
+                if (count1 != 0) {
+                    dest -= count1;
+                    cursor1 -= count1;
+                    len1 -= count1;
+                    System.arraycopy(a, cursor1 + 1, a, dest + 1, count1);
+                    if (len1 == 0)
+                        break outer;
+                }
+                a[dest--] = tmp[cursor2--];
+                if (--len2 == 1)
+                    break outer;
+
+                count2 = len2 - gallopLeft(a[cursor1], tmp, 0, len2, len2 - 1, c);
+                if (count2 != 0) {
+                    dest -= count2;
+                    cursor2 -= count2;
+                    len2 -= count2;
+                    System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2);
+                    if (len2 <= 1)  // len2 == 1 || len2 == 0
+                        break outer;
+                }
+                a[dest--] = a[cursor1--];
+                if (--len1 == 0)
+                    break outer;
+                minGallop--;
+            } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
+            if (minGallop < 0)
+                minGallop = 0;
+            minGallop += 2;  // Penalize for leaving gallop mode
+        }  // End of "outer" loop
+        this.minGallop = minGallop < 1 ? 1 : minGallop;  // Write back to field
+
+        if (len2 == 1) {
+            assert len1 > 0;
+            dest -= len1;
+            cursor1 -= len1;
+            System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
+            a[dest] = tmp[cursor2];  // Move first elt of run2 to front of merge
+        } else if (len2 == 0) {
+            throw new IllegalArgumentException(
+                "Comparison method violates its general contract!");
+        } else {
+            assert len1 == 0;
+            assert len2 > 0;
+            System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2);
+        }
+    }
+
+    /**
+     * Ensures that the external array tmp has at least the specified
+     * number of elements, increasing its size if necessary.  The size
+     * increases exponentially to ensure amortized linear time complexity.
+     *
+     * @param minCapacity the minimum required capacity of the tmp array
+     * @return tmp, whether or not it grew
+     */
+    private T[] ensureCapacity(int minCapacity) {
+        if (tmp.length < minCapacity) {
+            // Compute smallest power of 2 > minCapacity
+            int newSize = minCapacity;
+            newSize |= newSize >> 1;
+            newSize |= newSize >> 2;
+            newSize |= newSize >> 4;
+            newSize |= newSize >> 8;
+            newSize |= newSize >> 16;
+            newSize++;
+
+            if (newSize < 0) // Not bloody likely!
+                newSize = minCapacity;
+            else
+                newSize = Math.min(newSize, a.length >>> 1);
+
+            @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
+            T[] newArray = (T[]) new Object[newSize];
+            tmp = newArray;
+        }
+        return tmp;
+    }
+
+    /**
+     * Checks that fromIndex and toIndex are in range, and throws an
+     * appropriate exception if they aren't.
+     *
+     * @param arrayLen the length of the array
+     * @param fromIndex the index of the first element of the range
+     * @param toIndex the index after the last element of the range
+     * @throws IllegalArgumentException if fromIndex > toIndex
+     * @throws ArrayIndexOutOfBoundsException if fromIndex < 0
+     *         or toIndex > arrayLen
+     */
+    private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
+        if (fromIndex > toIndex)
+            throw new IllegalArgumentException("fromIndex(" + fromIndex +
+                       ") > toIndex(" + toIndex+")");
+        if (fromIndex < 0)
+            throw new ArrayIndexOutOfBoundsException(fromIndex);
+        if (toIndex > arrayLen)
+            throw new ArrayIndexOutOfBoundsException(toIndex);
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/TimSort/ArrayBuilder.java	Wed Jul 29 14:24:19 2009 -0700
@@ -0,0 +1,142 @@
+/*
+ * Copyright 2009 Google Inc.  All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+
+import java.util.Random;
+import java.math.BigInteger;
+
+public enum ArrayBuilder {
+
+    // These seven are from  Tim's paper (listsort.txt)
+
+    RANDOM_INT {
+        public Object[] build(int len) {
+            Integer[] result = new Integer[len];
+            for (int i = 0; i < len; i++)
+                result[i] = rnd.nextInt();
+            return result;
+        }
+    },
+
+    DESCENDING_INT {
+        public Object[] build(int len) {
+            Integer[] result = new Integer[len];
+            for (int i = 0; i < len; i++)
+                result[i] = len - i;
+            return result;
+        }
+    },
+
+    ASCENDING_INT {
+        public Object[] build(int len) {
+            Integer[] result = new Integer[len];
+            for (int i = 0; i < len; i++)
+                result[i] = i;
+            return result;
+        }
+    },
+
+    ASCENDING_3_RND_EXCH_INT {
+        public Object[] build(int len) {
+            Integer[] result = new Integer[len];
+            for (int i = 0; i < len; i++)
+                result[i] = i;
+            for (int i = 0; i < 3; i++)
+                swap(result, rnd.nextInt(result.length),
+                             rnd.nextInt(result.length));
+            return result;
+        }
+    },
+
+    ASCENDING_10_RND_AT_END_INT {
+        public Object[] build(int len) {
+            Integer[] result = new Integer[len];
+            int endStart = len - 10;
+            for (int i = 0; i < endStart; i++)
+                result[i] = i;
+            for (int i = endStart; i < len; i++)
+                result[i] = rnd.nextInt(endStart + 10);
+            return result;
+        }
+    },
+
+    ALL_EQUAL_INT {
+        public Object[] build(int len) {
+            Integer[] result = new Integer[len];
+            for (int i = 0; i < len; i++)
+                result[i] = 666;
+            return result;
+        }
+    },
+
+    DUPS_GALORE_INT {
+        public Object[] build(int len) {
+            Integer[] result = new Integer[len];
+            for (int i = 0; i < len; i++)
+                result[i] = rnd.nextInt(4);
+            return result;
+        }
+    },
+
+    RANDOM_WITH_DUPS_INT {
+        public Object[] build(int len) {
+            Integer[] result = new Integer[len];
+            for (int i = 0; i < len; i++)
+                result[i] = rnd.nextInt(len);
+            return result;
+        }
+    },
+
+    PSEUDO_ASCENDING_STRING {
+        public String[] build(int len) {
+            String[] result = new String[len];
+            for (int i = 0; i < len; i++)
+                result[i] = Integer.toString(i);
+            return result;
+        }
+    },
+
+    RANDOM_BIGINT {
+        public BigInteger[] build(int len) {
+            BigInteger[] result = new BigInteger[len];
+            for (int i = 0; i < len; i++)
+                result[i] = HUGE.add(BigInteger.valueOf(rnd.nextInt(len)));
+            return result;
+        }
+    };
+
+    public abstract Object[] build(int len);
+
+    public void resetRandom() {
+        rnd = new Random(666);
+    }
+
+    private static Random rnd = new Random(666);
+
+    private static void swap(Object[] a, int i, int j) {
+        Object t = a[i];
+        a[i] = a[j];
+        a[j] = t;
+    }
+
+    private static BigInteger HUGE = BigInteger.ONE.shiftLeft(100);
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/TimSort/README	Wed Jul 29 14:24:19 2009 -0700
@@ -0,0 +1,4 @@
+This directory contains benchmark programs used to compare the
+performance of the TimSort algorithm against the historic 1997
+implementation of Arrays.sort.  Any future benchmarking will require
+minor modifications.

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/TimSort/SortPerf.java	Wed Jul 29 14:24:19 2009 -0700
@@ -0,0 +1,66 @@
+/*
+ * Copyright 2009 Google Inc.  All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+
+import java.util.Arrays;
+
+public class SortPerf {
+    private static final int NUM_SETS = 5;
+    private static final int[] lengths = { 10, 100, 1000, 10000, 1000000 };
+
+    // Returns the number of repetitions as a function of the list length
+    private static int reps(int n) {
+        return (int) (12000000 / (n * Math.log10(n)));
+    }
+
+    public static void main(String[] args) {
+        Sorter.warmup();
+
+        System.out.print("Strategy,Length");
+        for (Sorter sorter : Sorter.values())
+            System.out.print("," + sorter);
+        System.out.println();
+
+        for (ArrayBuilder ab : ArrayBuilder.values()) {
+            for (int n : lengths) {
+                System.out.printf("%s,%d", ab, n);
+                int reps = reps(n);
+                Object[] proto = ab.build(n);
+                for (Sorter sorter : Sorter.values()) {
+                    double minTime = Double.POSITIVE_INFINITY;
+                    for (int set = 0; set < NUM_SETS; set++) {
+                        long startTime = System.nanoTime();
+                        for (int k = 0; k < reps; k++) {
+                            Object[] a = proto.clone();
+                            sorter.sort(a);
+                        }
+                        long endTime = System.nanoTime();
+                        double time = (endTime - startTime) / (1000000. * reps);
+                        minTime = Math.min(minTime, time);
+                    }
+                    System.out.printf(",%5f", minTime);
+                }
+                System.out.println();
+            }
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/TimSort/Sorter.java	Wed Jul 29 14:24:19 2009 -0700
@@ -0,0 +1,55 @@
+/*
+ * Copyright 2009 Google Inc.  All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+
+import java.util.*;
+
+public enum Sorter {
+    TIMSORT {
+        public void sort(Object[] array) {
+            ComparableTimSort.sort(array);
+        }
+    },
+    MERGESORT {
+        public void sort(Object[] array) {
+            Arrays.sort(array);
+        }
+    };
+
+    public abstract void sort(Object[] array);
+
+    public static void warmup() {
+        System.out.println("start warm up");
+        Integer[] gold = new Integer[10000];
+        Random random = new java.util.Random();
+        for (int i=0; i < gold.length; i++)
+            gold[i] = random.nextInt();
+
+        for (int i=0; i < 10000; i++) {
+            for (Sorter s : values()) {
+                Integer[] test= gold.clone();
+                s.sort(test);
+            }
+        }
+        System.out.println("  end warm up");
+    }
+}