What kind of sort does the sort method of a List type collection do? And what complexity do you have? (Nlogn, n, ...)
What kind of sort does the sort method of a List type collection do? And what complexity do you have? (Nlogn, n, ...)
java.util.List is an interface, but from Java 8 interfaces can provide a default implementation of a method. Since sort(Comparator<? super E> c) is a method that has been added in Java 8, to maintain compatibility with old code a default implementation has been added that uses a variant of the algorithm mergesort , which is of complexity O (n log n).
This variant is known as Timsort (no entry in Spanish, sorry) by the name of its creator, Tim Peters, a Python guru. It is not faster than the classic Mergesoft but it optimizes the use of memory.
The algorithm is the same as the static methods Collections.sort(List<E> list) and Collections.sort(List<T> list, Comparator<? super T> c) , which already existed previously to Java 8
These data are specified in the Java documentation on Collections , within Sort :
Implementation note: This implementation is a stable, adaptive, iterative merge that requires much less than ng (n) comparisons when the input array is partially sorted, while offering the performance of a traditional merge when the input array is randomly ordered . If the input array is nearly sorted, the implementation requires approximately n comparisons.
Translation:
Implementation Note: This implementation is a stable, adaptive, iterative mergesort that requires significantly less than
n lg(n)comparisons when the input array is partially ordered, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is almost ordered, the implementation requires approximatelyncomparisons.