How efficient is the collection.sort () function?

Question

How fast is collection.sort () function in Java? What algorithm was used? I came across this function in this answer , which sorts the 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 works in O (n (n-1)) time, and that would be pretty inefficient for a large list. I don’t think that this was how Collections.sort () was created, given how inefficient it is.

Answer 1

From the Documentation on Collection sort () method:

: , , mergesort, , n lg (n) , , , . , n . n/2 .

, O (n log n) . ( ), , O (n ^ 2).

Answer 2

:

: , , , n lg (n) , , , , , n . n/2 .

. : .

Tim Peters Python (TimSort). " - ", . 467-474, 1993 ., " ".

, , . n2 log (n), .