Java Sorting Basics
— print (last updated: Mar 31, 2009) — print

Select font size:
Sorting is one of the most common complex operations used. Database systems make use of sorting as a common method for data presentation to the user interface.

Create the NetBeans project SortDemo which with a Main class into which you can install and run these test programs. The only other thing you'll need is 
import java.util.*;

Sorting in Java

Java provides two built-in ways to do sorting: The descriptions of these algorithms and their usage can be seen in the Java Data Structures (java.util) document in the Arrays and Collections sections, respectively.

For an array, A, of any primitive types or any Object type, these are supported: 
Arrays.sort(A);
Arrays.sort(A, fromIndex, toIndex);
The Arrays.sort function also gives the ability to sort a range between two indices. The "toIndex" argument name is misleading since the sort range is really between fromIndex and toIndex – 1, inclusive. Thus these two calls are equivalent: 
Arrays.sort(A);      is the same as       Arrays.sort(A, 0, A.length);
For a list, L, of Comparable elements, this is defined: 
Collections.sort(L);
When no Comparator object is passed to a sort algorithm, sorting is done using the "natural order" of supposedly Comparable elements as defined by the compareTo function. The Collections.sort does a type-check that the elements are Comparable, but Arrays.sort can only do a run-time check.

All other sorting is done using a Comparator object, cmp, passed to the sort function. Here are the relevant calls: 
Arrays.sort(A, cmp);
Arrays.sort(A, fromIndex, toIndex, cmp);
Collections.sort(L, cmp);

Basic Example

This first example shows the sorting of an array or list of Integers using the natural order: 
  public static void mainBasic(String[] args) {
    Integer[] A = new Integer[20], B = new Integer[20];

    Random r = new Random();

    for (int i = 0; i < A.length; ++i) {
      A[i] = B[i] = new Integer(r.nextInt(40));
    }

    List<Integer> L = new ArrayList<Integer>(Arrays.asList(A));

    System.out.println("A:        " + Arrays.toString(A));
    Arrays.sort(A);
    System.out.println("A sorted: " + Arrays.toString(A));

    System.out.println();

    System.out.println("B:              " + Arrays.toString(B));
    Arrays.sort(B,3,7);
    System.out.println("B sorted (3,7): " + Arrays.toString(B));

    System.out.println();

    System.out.println("L:        " + L);
    Collections.sort(L);
    System.out.println("L sorted: " + L);
  }

Using a comparator

This second example shows the sorting of an array or list of Integers using a comparator. The comparator makes the Integer comparsion like String comparison. 
  public static void mainComparator(String[] args) {
    Integer[] A = new Integer[20];

    Random r = new Random();

    for (int i = 0; i < A.length; ++i) {
      A[i] = new Integer(r.nextInt(20));
    }

    Comparator<Integer> cmp = new Comparator<Integer>() {
      @Override
      public int compare(Integer lhs, Integer rhs) {
        return lhs.toString().compareTo(rhs.toString());
      }
    };

    List<Integer> L = new ArrayList<Integer>(Arrays.asList(A));

    System.out.println("A: " + Arrays.toString(A));
    Arrays.sort(A, cmp);
    System.out.println("A: " + Arrays.toString(A));

    System.out.println();

    System.out.println("L: " + L);
    Collections.sort(L, cmp);
    System.out.println("L: " + L);
  }

User-defined classes/Stability

This third example illustrates how sorting can be done on any user-defined class whatsoever by defining a suitable comparator for the class. The class we define called Email has data values consisting of a String from and an Date time. This program illustrates sorting in two ways, based on these two fields. 
  public static class Email {
    String from;
    Date time;

    Email( String from, Date time ) { this.from = from; this.time = time; }

    @Override
    public String toString() { return from + " : " + time; }
  }

  public static void mainStable(String[] args) {

    Email E[] = new Email[] {
      new Email( "bob",   new GregorianCalendar(2008, 10, 19).getTime() ),
      new Email( "john",  new GregorianCalendar(2008, 10, 15).getTime() ),
      new Email( "steve", new GregorianCalendar(2008, 10, 14).getTime() ),
      new Email( "john",  new GregorianCalendar(2008, 10, 18).getTime() ),
      new Email( "bob",   new GregorianCalendar(2008, 10, 16).getTime() ),
      new Email( "bob",   new GregorianCalendar(2008, 10, 12).getTime() ),
      new Email( "steve", new GregorianCalendar(2008, 10, 17).getTime() ),
      new Email( "john",  new GregorianCalendar(2008, 10, 13).getTime() )
    };

    Comparator<Email> cmp_from = new Comparator<Email>() {
      @Override
      public int compare(Email lhs, Email rhs) {
        return lhs.from.compareTo(rhs.from);
      }
    };

    Comparator<Email> cmp_time = new Comparator<Email>() {
      @Override
      public int compare(Email lhs, Email rhs) {
        return lhs.time.compareTo(rhs.time);
      }
    };

    System.out.println( "----------------- before" );
    for (Email e: E) { System.out.println(e); }

    Arrays.sort(E, cmp_time);  // sort by time

    System.out.println( "----------------- sorted by time" );
    for (Email e: E) { System.out.println(e); }

    Arrays.sort(E, cmp_from);  // sort by from

    System.out.println( "----------------- sorted by from" );
    for (Email e: E) { System.out.println(e); }
  }
The output of this program lookes like this: 
----------------- before
bob : Wed Nov 19 00:00:00 GMT-05:00 2008
john : Sat Nov 15 00:00:00 GMT-05:00 2008
steve : Fri Nov 14 00:00:00 GMT-05:00 2008
john : Tue Nov 18 00:00:00 GMT-05:00 2008
bob : Sun Nov 16 00:00:00 GMT-05:00 2008
bob : Wed Nov 12 00:00:00 GMT-05:00 2008
steve : Mon Nov 17 00:00:00 GMT-05:00 2008
john : Thu Nov 13 00:00:00 GMT-05:00 2008
----------------- sorted by time
bob : Wed Nov 12 00:00:00 GMT-05:00 2008
john : Thu Nov 13 00:00:00 GMT-05:00 2008
steve : Fri Nov 14 00:00:00 GMT-05:00 2008
john : Sat Nov 15 00:00:00 GMT-05:00 2008
bob : Sun Nov 16 00:00:00 GMT-05:00 2008
steve : Mon Nov 17 00:00:00 GMT-05:00 2008
john : Tue Nov 18 00:00:00 GMT-05:00 2008
bob : Wed Nov 19 00:00:00 GMT-05:00 2008
----------------- sort by from
bob : Wed Nov 12 00:00:00 GMT-05:00 2008
bob : Sun Nov 16 00:00:00 GMT-05:00 2008
bob : Wed Nov 19 00:00:00 GMT-05:00 2008
john : Thu Nov 13 00:00:00 GMT-05:00 2008
john : Sat Nov 15 00:00:00 GMT-05:00 2008
john : Tue Nov 18 00:00:00 GMT-05:00 2008
steve : Fri Nov 14 00:00:00 GMT-05:00 2008
steve : Mon Nov 17 00:00:00 GMT-05:00 2008

Stable sort

In the above example, the first sort orders the entries by time, the second sort orders by name. The fact that the entries which have the same name are still ordered by time means that the sorting algorithm used by Java is stable.

A stable sorting algorithm is one in which equal element retain their same relative ordering. In our case, all the "bob" elements which were ordered by time are equal with respect to sorting by the from field, and they are still ordered by time afterwards.

This stability feature is implicitly used in virtually every User Interface program which allows the user to list elements according to different characteristics.

© Robert M. Kline