Merge sort (Java)

From LiteratePrograms

Other implementations: ACL2 | C | C++ | dc | Eiffel | Erlang | Haskell | Java | JavaScript | Lisp | OCaml | Oz | Perl | Prolog | Python | Ruby | Scheme

Merge sort or mergesort is a simple but efficient sort algorithm that splits the list into two sublists, sorts each one, then combines them into a single sorted list. It has good worst-case performance and requires only sequential access, making it ideal for sequential data structures like linked lists. In this Java example we'll write a simple mergesort for arrays.

The Java standard class library provides Arrays.sort() and Collections.sort() methods for sorting arrays and lists, respectively. They are implemented using mergesort. In practice you should use one of these instead.

In these examples we will demonstrate the sort only for ints; in the future this may be generalised to arbitrary data.

To sort an array using mergesort, we split the array into two subarrays in an implicit way:

<<simple array mergesort>>=
public static void mergeSortArray(int[] a, int start, int end) {
    check termination condition
    mergeSortArray(a, start, start + ((end-start)/2));
    mergeSortArray(a, start + ((end-start)/2), end);
    merge the two sorted sublists
}

The tricky part is merging the two sorted subarrays. We have two ways to go about this:

1. Create a separate buffer the same size as the list for constructing the result of the merge in.
2. Attempt to rearrange elements as we go so that the portion of the merged list constructed so far does not overwrite sublist elements that are not yet merged.

The first option is simple but has a high memory overhead (linear auxilary memory) as well as a problem with frequent allocations. The second option is in-place and more efficient, but also more complicated. Here we stick to the simpler method:

<<array mergesort>>=
public static void mergeSortArray(int[] a, int start, int end) {
    mergesortArray variable declarations
    check termination condition
    mergeSortArray(a, start, start + ((end-start)/2));
    mergeSortArray(a, start + ((end-start)/2), end);
    merge the two sorted sublists into temp
    System.arraycopy(a, start, temp, start, end-start);
}

The System.arraycopy() at the end puts the final result back in a.

The merge operation itself is straightforward. We have two pointers starting at the beginning of each subarray, and we continually copy the smaller value into the result array and advance that value's pointer:

<<mergesortArray variable declarations>>=
int[] temp = new int[end];
int i1, i2, tempi;
<<merge the two sorted sublists into temp>>=
i1 = 0;
i2 = end/2;
tempi = 0;
while (i1 < end/2 && i2 < end) {
    if (a[i1] <= a[i2])
        temp[tempi++] = a[i1++];
    else
        temp[tempi++] = a[i2++];
}

If either pointer hits the end of its subarray before the other, the remaining values are simply copied from the remaining subarray:

<<merge the two sorted sublists into temp>>=
while (i1 < end/2) {
    temp[tempi++] = a[i1++];
}
while (i2 < end) {
    temp[tempi++] = a[i2++];
}

As with other divide-and-conquer sorts, the simplest termination condition is when the list becomes of size one or less:

<<simple check termination condition>>=
if ((start-end) <= 1) {
    return;
}

But more efficient is to switch to insertion sort for small enough lists, like this code from Insertion sort (C, simple):

<<constants>>=
private static final int minMergeSortListSize  =  32;
<<check termination condition>>=
if ((end-start) < minMergeSortListSize) {
    /* Use insertion sort for small datasets. */
    for (int i=start; i < end; i++) {
        int j, v = a[i];
        for (j = i - 1; j >= 0; j--) {
            if (a[j] <= v)
                break;
            a[j + 1] = a[j];
        }
        a[j + 1] = v;
    }
    return;
}

This completes the sort. We can try it out with this sample code, which generates a random array of a size specified on the command line, sorts it, then verifies that it is in order:

<<MergeSortArray.java>>=
class MergeSortArray {
    constants
    array mergesort
    public static void main(String[] argv) {
        int size = Integer.parseInt(argv[0]);
        int[] a = new int[size];
        java.util.Random rand = 
            new java.util.Random(System.currentTimeMillis());
        for (int i=0; i<size; i++) {
            a[i] = rand.nextInt() % size;
        }
        mergeSortArray(a, 0, size);
        for (int i=1; i<size; i++) {
            if (!(a[i-1] <= a[i])) {
                System.out.println("ERROR");
                System.exit(-1);
            }
        }
        System.out.println("SUCCESS");
        System.exit(0);
    }
}

Download code