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.


Need Your Help

Starting a process with inherited stdin/stdout/stderr in Java 6

java io process pipe

If I start a process via Java's ProcessBuilder class, I have full access to that process's standard in, standard out, and standard error streams as Java InputStreams and OutputStreams. However, I c...

Why does switching from AT&T to Intel syntax make this tutorial segfault using GAS?

assembly x86 intel gas att

I'm working through some of the tutorials on http://www.ibm.com/developerworks/linux/library/l-gas-nasm/index.html to familiarize myself with x86/x64. This tutorial code compiles and runs without a

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.