2  * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.

     2  * Copyright (c) 1997, 2014, Oracle and/or its affiliates. All rights reserved.

   418      * Sorts this list using the supplied {@code Comparator} to compare elements.

   418      * Sorts this list according to the order induced by the specified

   419      * {@link Comparator}.

   420      *

   421      * <p>All elements in this list must be <i>mutually comparable</i> using the

   422      * specified comparator (that is, {@code c.compare(e1, e2)} must not throw

   423      * a {@code ClassCastException} for any elements {@code e1} and {@code e2}

   424      * in the list).

   425      *

   426      * <p>If the specified comparator is {@code null} then all elements in this

   427      * list must implement the {@link Comparable} interface and the elements'

   428      * {@linkplain Comparable natural ordering} should be used.

   429      *

   430      * <p>This list must be modifiable, but need not be resizable.

   421      * The default implementation is equivalent to, for this {@code list}:

   433      * The default implementation obtains an array containing all elements in

   422      * <pre>Collections.sort(list, c)</pre>

   434      * this list, sorts the array, and iterates over this list resetting each

   435      * element from the corresponding position in the array. (This avoids the

   436      * n<sup>2</sup> log(n) performance that would result from attempting

   437      * to sort a linked list in place.)

   438      *

   439      * @implNote

   440      * This implementation is a stable, adaptive, iterative mergesort that

   441      * requires far fewer than n lg(n) comparisons when the input array is

   442      * partially sorted, while offering the performance of a traditional

   443      * mergesort when the input array is randomly ordered.  If the input array

   444      * is nearly sorted, the implementation requires approximately n

   445      * comparisons.  Temporary storage requirements vary from a small constant

   446      * for nearly sorted input arrays to n/2 object references for randomly

   447      * ordered input arrays.

   448      *

   449      * <p>The implementation takes equal advantage of ascending and

   450      * descending order in its input array, and can take advantage of

   451      * ascending and descending order in different parts of the same

   452      * input array.  It is well-suited to merging two or more sorted arrays:

   453      * simply concatenate the arrays and sort the resulting array.

   454      *

   455      * <p>The implementation was adapted from Tim Peters's list sort for Python

   456      * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">

   457      * TimSort</a>).  It uses techniques from Peter McIlroy's "Optimistic

   458      * Sorting and Information Theoretic Complexity", in Proceedings of the

   459      * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,

   460      * January 1993.

   438         Collections.sort(this, c);

   477         Object[] a = this.toArray();

   478         Arrays.sort(a, (Comparator) c);

   479         ListIterator<E> i = this.listIterator();

   480         for (Object e : a) {

   481             i.next();

   482             i.set((E) e);

   483         }