Sorts this list according to the order induced by the specified
{@link Comparator}.
<p>All elements in this list must be <i>mutually comparable</i> using the
specified comparator (that is, {@code c.compare(e1, e2)} must not throw
a {@code ClassCastException} for any elements {@code e1} and {@code e2}
in the list).
<p>If the specified comparator is {@code null} then all elements in this
list must implement the {@link Comparable} interface and the elements'
{@linkplain Comparable natural ordering} should be used.
<p>This list must be modifiable, but need not be resizable.
@implSpec
The final implementation obtains an array containing all elements in
this list, sorts the array, and iterates over this 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
to sort a linked list in place.)
@implNote
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.
<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 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 techniques 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 c the {@code Comparator} used to compare list elements.
A {@code null} value indicates that the elements'
{@linkplain Comparable natural ordering} 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 list's list-iterator does
not support the {@code set} operation
@throws IllegalArgumentException
(<a href="Collection.html#optional-restrictions">optional</a>)
if the comparator is found to violate the {@link Comparator}
contract
Sorts this list according to the order induced by the specified {@link Comparator}.
<p>All elements in this list must be <i>mutually comparable</i> using the specified comparator (that is, {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} for any elements {@code e1} and {@code e2} in the list).
<p>If the specified comparator is {@code null} then all elements in this list must implement the {@link Comparable} interface and the elements' {@linkplain Comparable natural ordering} should be used.
<p>This list must be modifiable, but need not be resizable.
@implSpec The final implementation obtains an array containing all elements in this list, sorts the array, and iterates over this 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 to sort a linked list in place.)
@implNote 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.
<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 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 techniques 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 c the {@code Comparator} used to compare list elements. A {@code null} value indicates that the elements' {@linkplain Comparable natural ordering} 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 list's list-iterator does not support the {@code set} operation @throws IllegalArgumentException (<a href="Collection.html#optional-restrictions">optional</a>) if the comparator is found to violate the {@link Comparator} contract