| 100 |
|
|
| 101 |
|
/** |
| 102 |
|
* Sorts the specified list into ascending order, according to the |
| 103 |
< |
* <i>natural ordering</i> of its elements. All elements in the list must |
| 104 |
< |
* implement the <tt>Comparable</tt> interface. Furthermore, all elements |
| 105 |
< |
* in the list must be <i>mutually comparable</i> (that is, |
| 106 |
< |
* <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt> |
| 107 |
< |
* for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p> |
| 108 |
< |
* |
| 109 |
< |
* This sort is guaranteed to be <i>stable</i>: equal elements will |
| 110 |
< |
* not be reordered as a result of the sort.<p> |
| 111 |
< |
* |
| 112 |
< |
* The specified list must be modifiable, but need not be resizable.<p> |
| 113 |
< |
* |
| 114 |
< |
* The sorting algorithm is a modified mergesort (in which the merge is |
| 115 |
< |
* omitted if the highest element in the low sublist is less than the |
| 116 |
< |
* lowest element in the high sublist). This algorithm offers guaranteed |
| 117 |
< |
* n log(n) performance. |
| 103 |
> |
* {@linkplain Comparable natural ordering} of its elements. |
| 104 |
> |
* All elements in the list must implement the {@link Comparable} |
| 105 |
> |
* interface. Furthermore, all elements in the list must be |
| 106 |
> |
* <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} |
| 107 |
> |
* must not throw a {@code ClassCastException} for any elements |
| 108 |
> |
* {@code e1} and {@code e2} in the list). |
| 109 |
> |
* |
| 110 |
> |
* <p>This sort is guaranteed to be <i>stable</i>: equal elements will |
| 111 |
> |
* not be reordered as a result of the sort. |
| 112 |
> |
* |
| 113 |
> |
* <p>The specified list must be modifiable, but need not be resizable. |
| 114 |
> |
* |
| 115 |
> |
* <p>Implementation note: This implementation is a stable, adaptive, |
| 116 |
> |
* iterative mergesort that requires far fewer than n lg(n) comparisons |
| 117 |
> |
* when the input array is partially sorted, while offering the |
| 118 |
> |
* performance of a traditional mergesort when the input array is |
| 119 |
> |
* randomly ordered. If the input array is nearly sorted, the |
| 120 |
> |
* implementation requires approximately n comparisons. Temporary |
| 121 |
> |
* storage requirements vary from a small constant for nearly sorted |
| 122 |
> |
* input arrays to n/2 object references for randomly ordered input |
| 123 |
> |
* arrays. |
| 124 |
> |
* |
| 125 |
> |
* <p>The implementation takes equal advantage of ascending and |
| 126 |
> |
* descending order in its input array, and can take advantage of |
| 127 |
> |
* ascending and descending order in different parts of the the same |
| 128 |
> |
* input array. It is well-suited to merging two or more sorted arrays: |
| 129 |
> |
* simply concatenate the arrays and sort the resulting array. |
| 130 |
> |
* |
| 131 |
> |
* <p>The implementation was adapted from Tim Peters's list sort for Python |
| 132 |
> |
* (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> |
| 133 |
> |
* TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic |
| 134 |
> |
* Sorting and Information Theoretic Complexity", in Proceedings of the |
| 135 |
> |
* Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, |
| 136 |
> |
* January 1993. |
| 137 |
|
* |
| 138 |
< |
* This implementation dumps the specified list into an array, sorts |
| 138 |
> |
* <p>This implementation dumps the specified list into an array, sorts |
| 139 |
|
* the array, and iterates over the list resetting each element |
| 140 |
|
* from the corresponding position in the array. This avoids the |
| 141 |
|
* n<sup>2</sup> log(n) performance that would result from attempting |
| 145 |
|
* @throws ClassCastException if the list contains elements that are not |
| 146 |
|
* <i>mutually comparable</i> (for example, strings and integers). |
| 147 |
|
* @throws UnsupportedOperationException if the specified list's |
| 148 |
< |
* list-iterator does not support the <tt>set</tt> operation. |
| 149 |
< |
* @see Comparable |
| 148 |
> |
* list-iterator does not support the {@code set} operation. |
| 149 |
> |
* @throws IllegalArgumentException (optional) if the implementation |
| 150 |
> |
* detects that the natural ordering of the list elements is |
| 151 |
> |
* found to violate the {@link Comparable} contract |
| 152 |
|
*/ |
| 153 |
|
public static <T extends Comparable<? super T>> void sort(List<T> list) { |
| 154 |
|
Object[] a = list.toArray(); |
| 164 |
|
* Sorts the specified list according to the order induced by the |
| 165 |
|
* specified comparator. All elements in the list must be <i>mutually |
| 166 |
|
* comparable</i> using the specified comparator (that is, |
| 167 |
< |
* <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt> |
| 168 |
< |
* for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p> |
| 167 |
> |
* {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} |
| 168 |
> |
* for any elements {@code e1} and {@code e2} in the list). |
| 169 |
|
* |
| 170 |
< |
* This sort is guaranteed to be <i>stable</i>: equal elements will |
| 171 |
< |
* not be reordered as a result of the sort.<p> |
| 170 |
> |
* <p>This sort is guaranteed to be <i>stable</i>: equal elements will |
| 171 |
> |
* not be reordered as a result of the sort. |
| 172 |
|
* |
| 173 |
< |
* The sorting algorithm is a modified mergesort (in which the merge is |
| 153 |
< |
* omitted if the highest element in the low sublist is less than the |
| 154 |
< |
* lowest element in the high sublist). This algorithm offers guaranteed |
| 155 |
< |
* n log(n) performance. |
| 173 |
> |
* <p>The specified list must be modifiable, but need not be resizable. |
| 174 |
|
* |
| 175 |
< |
* The specified list must be modifiable, but need not be resizable. |
| 176 |
< |
* This implementation dumps the specified list into an array, sorts |
| 175 |
> |
* <p>Implementation note: This implementation is a stable, adaptive, |
| 176 |
> |
* iterative mergesort that requires far fewer than n lg(n) comparisons |
| 177 |
> |
* when the input array is partially sorted, while offering the |
| 178 |
> |
* performance of a traditional mergesort when the input array is |
| 179 |
> |
* randomly ordered. If the input array is nearly sorted, the |
| 180 |
> |
* implementation requires approximately n comparisons. Temporary |
| 181 |
> |
* storage requirements vary from a small constant for nearly sorted |
| 182 |
> |
* input arrays to n/2 object references for randomly ordered input |
| 183 |
> |
* arrays. |
| 184 |
> |
* |
| 185 |
> |
* <p>The implementation takes equal advantage of ascending and |
| 186 |
> |
* descending order in its input array, and can take advantage of |
| 187 |
> |
* ascending and descending order in different parts of the the same |
| 188 |
> |
* input array. It is well-suited to merging two or more sorted arrays: |
| 189 |
> |
* simply concatenate the arrays and sort the resulting array. |
| 190 |
> |
* |
| 191 |
> |
* <p>The implementation was adapted from Tim Peters's list sort for Python |
| 192 |
> |
* (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> |
| 193 |
> |
* TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic |
| 194 |
> |
* Sorting and Information Theoretic Complexity", in Proceedings of the |
| 195 |
> |
* Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, |
| 196 |
> |
* January 1993. |
| 197 |
> |
* |
| 198 |
> |
* <p>This implementation dumps the specified list into an array, sorts |
| 199 |
|
* the array, and iterates over the list resetting each element |
| 200 |
|
* from the corresponding position in the array. This avoids the |
| 201 |
|
* n<sup>2</sup> log(n) performance that would result from attempting |
| 203 |
|
* |
| 204 |
|
* @param list the list to be sorted. |
| 205 |
|
* @param c the comparator to determine the order of the list. A |
| 206 |
< |
* <tt>null</tt> value indicates that the elements' <i>natural |
| 206 |
> |
* {@code null} value indicates that the elements' <i>natural |
| 207 |
|
* ordering</i> should be used. |
| 208 |
|
* @throws ClassCastException if the list contains elements that are not |
| 209 |
|
* <i>mutually comparable</i> using the specified comparator. |
| 210 |
|
* @throws UnsupportedOperationException if the specified list's |
| 211 |
< |
* list-iterator does not support the <tt>set</tt> operation. |
| 212 |
< |
* @see Comparator |
| 211 |
> |
* list-iterator does not support the {@code set} operation. |
| 212 |
> |
* @throws IllegalArgumentException (optional) if the comparator is |
| 213 |
> |
* found to violate the {@link Comparator} contract |
| 214 |
|
*/ |
| 215 |
|
public static <T> void sort(List<T> list, Comparator<? super T> c) { |
| 216 |
|
Object[] a = list.toArray(); |
