Best way to sort in Java

Some may wonder whether a quick and dirty insertion sort implementation would be better than writing out a longer quicksort, with embedded sort order rules. Actually they are both wrong, at least in the world of professional Java programming. The correct way to sort in Java is: Collections.sort(list); (Swap "Collections" with "Arrays" if you are working with arrays instead of lists --arrays have a known constant speed performance, so it may be of interest to you. Collections is a class in the Java Collections package (java.util.*). See footnote for others.) Not only is this generally faster than a custom implementation, it also phenomenally reduces your code length thereby increase legibility, reduce code maintenance time, and reduce chances for bugs. A great sort implementation is already provided to you. Please don't custom implement that sort.

Custom sorting rules
By default, the sort algorithm uses the list items' implementation of Comparable interface to sort itself. If the default is inadequate for your needs, you can either (A) implement the Comparable interface yourself, or (B) implement a Comparator interface, and use it for example: Collections.sort(list, comparator);. A Comparable object specifies how to sort itself, while a Comparator is like a tool you can use to specify how to sort others. Here's a full-fledged example:

(Contents of file Example.java)

import java.util.*;
import java.io.PrintStream;

// This example code is released under the public domain.
// Author: tongpoo
// Java 1.5 code -- remove Generics code for 1.4.* compatibility.
class Example implements Comparable<Example> {
    private String foo, bar;
    public Example(String foo, String bar) {
        // this is how we are going to handle the null pointer case.
        if (foo == null || bar == null) {
            throw new NullPointerException();
        }
        this.foo = foo;
        this.bar = bar;
    }
    
    public String getFoo() {
        return foo;
    }
    
    public String getBar() {
        return bar;
    }
    
    // this is the part where you can add ordering logic.
    public int compareTo(Example obj) {
        if (this == obj) {
            // pointers are equivalent
            return 0;
        }
        int cmp;
        cmp = this.getFoo().compareTo(obj.getFoo());
        if (cmp == 0) {
            cmp = this.getBar().compareTo(obj.getBar());
        }
        return cmp;
    }
    
    // String representation
    public String toString() {
        return "[foo = '"+getFoo()+"', bar = '"+getBar()+"']";
    }


    /* for brevity, the call to sorting is done inside the
       same class in this example, but doesn't have to be. */
    public static void main(String[] args) {
        List<Example> list;
        PrintStream out;
        
        out = System.out;
        // Uncomment the section below if you
        //  are going to be running this on OS X:
        //try {
        //    out = new PrintStream(out, true, "UTF-8");
        //}
        //catch (java.io.UnsupportedEncodingException x) {
        //    // dead code space
        //}

        // sort example using the Comparable implementation.
        list = getExampleList();
        Collections.sort(list);
        out.println("Sort by foo first:");
        printList(out, list);

        // see what it looks like using the Comparator interface.
        list = getExampleList();
        Collections.sort(list, new Comparator<Example>() {

            // different sorting rule as an example
            public int compare(Example e1, Example e2) {
                if (e1 == e2) {
                    // pointers are equivalent
                    return 0;
                }
                int cmp;
                cmp = e1.getBar().compareTo(e2.getBar());
                if (cmp == 0) {
                    cmp = e1.getFoo().compareTo(e2.getFoo());
                }
                return cmp;
            }
        });
        out.println("Sort by bar first:");
        printList(out, list);
    }
    
    private static List<Example> getExampleList() {
        Example obj1 = new Example("hello", "world");
        Example obj2 = new Example("goodbye", "\u307f\u306a\u3055\u3093");
        Example obj3 = new Example("hello", "\u307f\u306a\u3055\u3093");
        ArrayList<Example> list = new ArrayList<Example>();
        list.add(obj1);
        list.add(obj2);
        list.add(obj3);
        return list;
    }
    
    private static void printList(PrintStream out, List<Example> list) {
        int size = list.size();
        for (int i = 0; i < size; i ++) {
            out.println(i+": "+list.get(i).toString());
        }
        out.println();
    }
}

---

The output:

Sort by foo first:
0: [foo = 'goodbye', bar = 'みなさん']
1: [foo = 'hello', bar = 'world']
2: [foo = 'hello', bar = 'みなさん']

Sort by bar first:
0: [foo = 'hello', bar = 'world']
1: [foo = 'goodbye', bar = 'みなさん']
2: [foo = 'hello', bar = 'みなさん']

Footnotes:
Relevant APIs:

• http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Comparable.html
• http://java.sun.com/j2se/1.4.2/docs/api/java/util/Arrays.html
• http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html
• http://java.sun.com/j2se/1.4.2/docs/api/java/util/Comparator.html

Code tweaked Wednesday, December 2, 2009 at 0:33
And again on Wednesday, December 2, 2009 at 3:30 (removed harmless but unnecessary implementation of Comparator.equals )