# How efficient is the collection.sort() function?

How fast is the collection.sort() function in Java? What algorithm was used? I came across this function in this answer that sorts a list in descending order:

public static void main(String arg[]) { List<Double> testList=new ArrayList(); /*Adding The values to the List*/ testList.add(0.5); testList.add(0.2); testList.add(0.9); testList.add(0.1); testList.add(0.1); testList.add(0.1); testList.add(0.54); testList.add(0.71); testList.add(0.71); testList.add(0.71); testList.add(0.92); testList.add(0.12); testList.add(0.65); testList.add(0.34); testList.add(0.62); /*Declare a new List for storing sorted Results*/ List<Double> finalList=new ArrayList(); while(!testList.isEmpty()) //perform operation until all elements are moved to new List { double rank=0; int i=0; for(double d: testList) { if(d>=rank) { rank=d; } } finalList.add(rank); testList.remove(testList.indexOf(rank)); } for(double d : finalList) { System.out.println(d); } }

I think this runs in O(n(n-1)) time and it would be pretty inefficient for a large list. I don't believe this is how Collections.sort() was created considering how inefficient it is.

## Answers

From the Documentation on Collection's method sort():

Implementation note: **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.

It means that is **O(n log n)** in the **worst case**. So YES it's very fast (even in the worst case), much faster than a O(n^2) sorting algorithm.