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

equal deleted inserted replaced

-:b2b1848b52ab
+:6c67737a5ac0
 /*
-* Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
+* Copyright (c) 1997, 2014, Oracle and/or its affiliates. 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.  Oracle designates this
 * <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.
 *
-* <p>Implementation note: This implementation is a stable, adaptive,
+* @implNote
-* iterative mergesort that requires far fewer than n lg(n) comparisons
+* This implementation defers to the {@link List#sort(Comparator)}
-* when the input array is partially sorted, while offering the
+* method using the specified list and a {@code null} comparator.
-* 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.
-*
-* <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
-* to sort a linked list in place.
 *
 * @param  <T> the class of the objects in the list
 * @param  list the list to be sorted.
 * @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 {@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
+* @see List#sort(Comparator)
 */
 @SuppressWarnings("unchecked")
 public static <T extends Comparable<? super T>> void sort(List<T> list) {
-Object[] a = list.toArray();
+list.sort(null);
-Arrays.sort(a);
-ListIterator<T> i = list.listIterator();
-for (Object e : a) {
-i.next();
-i.set((T) e);
-}
 }
 /**
 * Sorts the specified list according to the order induced by the
 * specified comparator.  All elements in the list must be <i>mutually
 * <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.
 *
-* <p>Implementation note: This implementation is a stable, adaptive,
+* @implNote
-* iterative mergesort that requires far fewer than n lg(n) comparisons
+* This implementation defers to the {@link List#sort(Comparator)}
-* when the input array is partially sorted, while offering the
+* method using the specified list and comparator.
-* 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.
-*
-* <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
-* to sort a linked list in place.
 *
 * @param  <T> the class of the objects in the list
 * @param  list the list to be sorted.
 * @param  c the comparator to determine the order of the list.  A
 *        {@code null} value indicates that the elements' <i>natural
 *         <i>mutually comparable</i> using the specified comparator.
 * @throws UnsupportedOperationException if the specified list's
 *         list-iterator does not support the {@code set} operation.
 * @throws IllegalArgumentException (optional) if the comparator is
 *         found to violate the {@link Comparator} contract
+* @see List#sort(Comparator)
 */
 @SuppressWarnings({"unchecked", "rawtypes"})
 public static <T> void sort(List<T> list, Comparator<? super T> c) {
-Object[] a = list.toArray();
+list.sort(c);
-Arrays.sort(a, (Comparator)c);
-ListIterator<T> i = list.listIterator();
-for (Object e : a) {
-i.next();
-i.set((T) e);
-}
 }
 /**
 * Searches the specified list for the specified object using the binary
 *
 * <p>This example illustrates the type-safe way to obtain an empty list:
 * <pre>
 *     List&lt;String&gt; s = Collections.emptyList();
 * </pre>
-* Implementation note:  Implementations of this method need not
+*
-* create a separate <tt>List</tt> object for each call.   Using this
+* @implNote
-* method is likely to have comparable cost to using the like-named
+* Implementations of this method need not create a separate <tt>List</tt>
-* field.  (Unlike this method, the field does not provide type safety.)
+* object for each call.   Using this method is likely to have comparable
+* cost to using the like-named field.  (Unlike this method, the field does
+* not provide type safety.)
 *
 * @param <T> type of elements, if there were any, in the list
 * @return an empty immutable list
 *
 * @see #EMPTY_LIST

changeset 22285	6c67737a5ac0
parent 22078	bdec5d53e98c
child 23746	ce60f7b62312