Next: None. Up: Recursion. Previous: Towers of Hanoi.

Mergesort

Mergesort algorithm

The final sorting algorithm we'll examine in the class works using an algorithmic design technique called divide and conquer. In this case, we first split the array into two halves, then we sort each half (using the same procedure - i.e., we make a recursive call), and finally we merge the two halves together. The base case would be when the array has only one element in it, in which case it is already sorted. This algorithm is called Mergesort.

Java code

Writing Mergesort in Java is significantly more complex that writing selection sort or insertion sort: The basic procedure (the sort() method) isn't bad. But merging two arrays into one is a relatively complex to write itself. (It's implemented below in the merge() method. Basically, it starts at the front of both arrays to be merged; the minimum of these goes at the front of the merged array. And then it can step to the next element of the array to repeat the process to see which is second, which is third, etc.) This implementation also defines a method extract() for extracting a subarray of a larger, known array.

public class MergeSort {
    // sort: reorders the elements of elts so that they are in
    // increasing order.
    public static void sort(int[] elts) {
        if(elts.length > 1) {
            // split the array into two pieces, as close to the same
            // size as possible.
            int[] first = extract(elts, 0, elts.length / 2);
            int[] last = extract(elts, elts.length / 2, elts.length);

            // sort each of the two halves recursively
            sort(first);
            sort(last);

            // merge the two sorted halves together
            merge(elts, first, last);
        }
    }

    // extract: returns a subarray of elts, starting with index
    // start in elts, continuing to (but not including) index
    // last.
    private static int[] extract(int[] elts, int start, int last) {
        int[] ret = new int[last - start];
        for(int i = 0; i < ret.length; i++) ret[i] = elts[start + i];
        return ret;
    }

    // merge: merges arrays a and b, placing the result into the
    // array dest. This only works if both a and b are already in
    // increasing order.
    private static void merge(int[] dest, int[] a, int[] b) {
        int i = 0;
        int j = 0;
        while(i < a.length && j < b.length) {
            if(a[i] < b[j]) {
                dest[i + j] = a[i];
                ++i;
            } else {
                dest[i + j] = b[j];
                ++j;
            }
        }
        for(; i < a.length; i++) dest[i + j] = a[i];
        for(; j < b.length; j++) dest[i + j] = b[j];
    }
}

(From a programming point of view, this particular implementation is pretty inefficient: It allocates quite a bit more memory than necessary, which wastes a lot of time. I've sacrificed efficiency for readability here, which is fine, since optimizing to this level of detail isn't really a part of this course. But I just wanted to include this little footnote to point out that all this memory allocation isn't the best way of going about this program.)

Theoretical time analysis

To get a feel for how this works, we first analyze the process of extracting two subarrays and merging the two subarrays. If the original array has n elements, then both of these take O(n) time. (In the extract() method, this is easy to see. In the merge() method, you can convince yourself of this by observing that, each time through any of the loops, the sum i + j increases by 1. This sum begins at 0, and it never exceeds n, so the total number of times through all the loops must be at most n (and in fact it's exactly n).)

With this observation, we could define a recurrence T(n) representing how much time it takes to Mergesort an array of length n.

          O(1)                      if n <= 1
T(n) <= {
          O(n) + 2 T(n / 2) + O(n)  otherwise

Unfortunately, we haven't the mathematical machinery to do this right now. But there's an easier way. Let's assume that n is a power of 2, to simplify our analysis. Then let's draw a recursion tree.

Say we're at a node handling an array of length k. For this node, the time spent outside the recursive calls is O(k) - after all, it takes O(k) time to split the array into two and O(k) time to merge the two sorted arrays together. (And for the base cases at the bottom, for all of which k=1, it takes O(1) time to simply return having changed nothing.)

We'll sum up the times for each node, by summing by horizontal levels. For each level, the sum of the times for each node is O(n). Since the size of the arrays in each level halves each time we go down, we can immediately see that there are 1 + log₂ n levels. So the total amount of time is O(n log₂ n).

This is dramatically better than O(n²). But that's a theoretical result, and you might justifiably wonder how it compares in practice.

Experimental speed analysis

To see how Mergesort performs in practice, I used the code from today and last time, and wrote a short program to time the various algorithms on different sizes of arrays. Here are the numbers I collected. (Times are in milliseconds, measured on a SunBlade 100, which has a 500MHz SPARC chip in it.)

You can see that for small arrays (less than 200 elements), all three techniques do well (and in fact sometimes Mergesort does worse than the other two). But, as the arrays get to be moderately large, it quickly does quite a bit better.

Plus, the Mergesort I timed wasn't very optimized. If I really wanted to write decent Mergesort code, I could easily cut its computation time to a fraction of the measured time. (In fact, I wrote an optimized version, which takes a third of the time of the MergeSort presented above (pretty much regardless of array size).) The same isn't true of insertion sort or selection sort, both of which are very close to the best possible implementation.

(As a footnote, I also tried to do some timings with C++, just to see how it would perform relative to the Java code. Since the Java code is running under the JVM, it has an inherent disadvantage, and I expected to see the C++ program doing much better. Surprisingly, the straightforward C++ translation of the above Mergesort code seemed to do about 50% worse than the Java code. The C++ translation of the optimized Java version, however, ran three times as fast as its Java equivalent - that is, 9 times as fast as the straightforward Java code above: on a random length-1000 array, it took only 0.101 milliseconds to sort.)

Next: None. Up: Recursion. Previous: Towers of Hanoi.