Sorting algorithms for Java lists

Some time ago I was giving advice to someone asking for sorting algorithms. He specifically asked about the bubblesort algorithm, which is often showed as a first algorithm in computer sience programs.

However - it ended up with me creating a small library containing the four most used algorithms for sorting (bubble sort, heapsort, merge sort and quicksort) Java lists. I will go through these four algorithms and show you my implementation of them.

I'm sure someone could write better implementations than mine and I don't preferr these implementations over Javas built in Collections.sort() method - it is generally faster than mine and has a good implementation (which I will show you as well).

First out: Bubble sort

Bubble sort is the easiest sorting algorithm to understand, it loops through the entire list comparing values in each loop and swapping them if there's an order mismatch. Worst case performance of O(n^2) (read up on Big-O notation?).

The algorithm uses two nested loops, here's a generic skeleton:

/*
 * Since is pass-by-reference language (for objects),
 * there's no need to return anything
 */
public void bubblesort(List list) {
    /*
     * Outer loop goes through the entire list
     */
    for (int i = 0; i < list.size(); i++) {
        /*
         * Inner loop only needs to go from the top
         * of the list to the current element from
         * the outer loop - the rest of the list is
         * already sorted
         */
        for (int j = list.size() - 1; j > i; j--) {
            /*
             * If the items are in the wrong order,
             * we swap them
             */
            if (list.get(j) < list.get(j - 1))
                Collections.swap(list, j, j - 1);
        }
    }
}

Since Java 1.5 we're able to determine if the objects are comparable using generics, which I think is a good idea. Java also have a Comparable interface, giving us more security for type checking. Here's my implementation which uses generics and only accepts Lists of the Comparable type (or Lists of objects that implements Comparable):

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    for (int i = 0; i < list.size(); i++) {
        for (int j = list.size() - 1; j > i; j--) {
	        if (list.get(j).compareTo(list.get(j - 1)) < 0)
		        Collections.swap(list, j, j - 1);
        }
    }
}

Heapsort

Next up is heapsort, an in-place algorithm with a worst case performance of O(n log n). It builds up a heap from the list, does the comparison, reorganize the list if the comparison showed the items were in the wrong order and then rebuilds the heap.

My implementation of heapsort looks like this:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    for (int i = list.size() / 2; i >= 0; i--)
        buildHeap(list, i, list.size());
    for (int i = list.size() - 1; i > 0; i--) {
        Collections.swap(list, 0, i);
        buildHeap(list, 0, i);
    }
}
private static <T extends Comparable<? super T>> void buildHeap(List<T> list, int a, int b) {
    int child = 0;
    T tmp;

    for (tmp = list.get(a); (2 * a + 1) < b; a = child) {
        child = 2 * a + 1;
        if (child != b - 1 && list.get(child).compareTo(list.get(child + 1)) < 0)
	        child++;
        if (tmp.compareTo(list.get(child)) < 0)
	        list.set(a, list.get(child));
        else
	        break;
    }
    list.set(a, tmp);
}

Merge sort

Merge sort is a recursive sorting algorithm, which divides the unsorted list in to sublists, and runs merge sort on each of the two lists and merges the lists back together on it's way back in the recursive call. The worst case performance is the same as heapsort, O(n log n).

My implementation uses a temporary list for storing values:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    List<T> tmp = new ArrayList<T>(list.size());
    /*
     * Need to fill the list with null-values
     * to prevent IndexOfOfBoundsException
     */
    for (int i = 0; i < list.size(); i++)
        tmp.add(null);
    
    sort(list, tmp, 0, list.size()-1);
}
private static <T extends Comparable<? super T>> void sort(List<T> list, List<T> tmp, int left, int right) {
    if (left < right) {
        int middle = (left + right) / 2;
        sort(list, tmp, left, middle);
        sort(list, tmp, middle+1, right);
        merge(list, tmp, left, middle+1, right);
    }
}
private static <T extends Comparable<? super T>> void merge(List<T> list, List<T> tmp, int leftPos, int rightPos, int rightEnd) {
    int leftEnd     = rightPos - 1;
    int tmpPos      = leftPos;
    int numElements = rightEnd - leftPos + 1;
    
    while (leftPos <= leftEnd && rightPos <= rightEnd) {
        if (list.get(leftPos).compareTo(list.get(rightPos)) < 0)
            tmp.set(tmpPos++, list.get(leftPos++));
        else
            tmp.set(tmpPos++, list.get(rightPos++));
    }
    while(leftPos <= leftEnd) {
        tmp.set(tmpPos++, list.get(leftPos++));
    }
    while(rightPos <= rightEnd) {
        tmp.set(tmpPos++, list.get(rightPos++));
    }
    for (int i = 0; i < numElements; i++, rightEnd--) {
        list.set(rightEnd, tmp.get(rightEnd));
    }
}

Quicksort

Quicksort is probably the most well-known sorting algorithm out there. On average the it makes O(n log n) performance, but in worst case it's O(n^2) - but it's rare in a good implementation.

A simple implementation for Java lists:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    if (list.size() <= 1)
        return;
    
    List<T> less    = new ArrayList<T>();
    List<T> greater = new ArrayList<T>();
    
    T pivot = list.remove(list.size() / 2);
    
    for (T element : list) {
        if (element.compareTo(pivot) < 0)
            less.add(element);
        else
            greater.add(element);
    }
    sort(less);
    sort(greater);
    list.clear();
    list.addAll(less);
    list.add(pivot);
    list.addAll(greater);
}

Using a partition algorithm makes quicksort use up less memory. My implementation:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    sort(list, 0, list.size() - 1);
}
public static <T extends Comparable<? super T>> void sort(List<T> list, int low, int high) {
    if (high > low) {
        int pivotIndex = list.size() / 2;
        pivotIndex     = partition(list, low, high, pivotIndex);
        sort(list, low, pivotIndex - 1);
        sort(list, pivotIndex + 1, high);
    }
}
public static <T extends Comparable<? super T>> int partition(List<T> list, int low, int high, int pivotIndex) {
    T pivot = list.get(pivotIndex);
    Collections.swap(list, pivotIndex, high);

    int index = low;
    for (int i = low; i < high; i++) {
        if (list.get(i).compareTo(pivot) < 0)
	        Collections.swap(list, i, index++);
    }

    Collections.swap(list, high, index);

    return index;
}

The demo code

The demo code available for this article contains a runnable jar-file, containing the sources, unit tests and an example application with a timer which times the different algorithms. Run it from a command line like this:

$> java -jar sorting.jar

Björn Wikström, 2010-01-17