Sort method Sort of the Java List interface

-1

What kind of sort does the sort method of a List type collection do? And what complexity do you have? (Nlogn, n, ...)

    
asked by OKOK 01.12.2017 в 11:21
source

2 answers

-1

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

    
answered by 01.12.2017 в 12:07
-2

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 approximately n comparisons.

    
answered by 01.12.2017 в 11:49