Merge Sort Java Implementation

Question

Can someone check my Merge Sort implementation on Java? Is it good/bad and can it be improved further?

public class MyMergeSort {
    private int [] data;

    public MyMergeSort(int[] data){
        this.data = data;
    }

    public int[] sort(int[] data){
        if (data.length < 2){
            return data;
        }
        int mid = data.length/2;
        int first[] = new int[mid];
        int second[] = new int[data.length - mid];
        System.arraycopy(data, 0, first, 0, mid);
        System.arraycopy(data, mid, second, 0, data.length - mid);
        return merge(sort(first), sort(second));
    }

    private int[] merge(int[] arr1, int[] arr2) {
        if(arr1.length == 0){
            return arr2;
        }
        if(arr2.length == 0){
            return arr1;
        }
        int res[] = new int[arr1.length + arr2.length];
        int i;
        int j = 0; // iterate over the first array
        int k  = 0; // iterate over the second array
        for (i = 0; i < res.length; i++) {
            if(j < arr1.length && k < arr2.length){
                if(arr1[j] < arr2[k]){
                    res[i] = arr1[j];
                    j++;
                }
                else{
                    res[i] = arr2[k];
                    k++;
                }
            }
            else{
                if(j < arr1.length){
                    System.arraycopy(arr1, j, res, i, arr1.length-j);
                    break;
                }
                else{
                    System.arraycopy(arr2, k, res, i, arr2.length-k);
                    break;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int d[] = {1, 9, 2, 8, 6, 3, 7, 4, 2};
        MyMergeSort mySort = new MyMergeSort(d);
        int res[] = new int[d.length];
        res =  mySort.sort(d);
        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i] + " ");
        }
    }
}

Answer 1

• Be consistent with your formatting. Sometimes you have a space between keywords like if and else and the opening parenthesis and the closing parenthesis and the opening brace, sometimes not. Pick one (I prefer a space) and stick with it. I also put spaces around all binary operators: data.length / 2 to match i < res.length. Again, consistency helps readability.

• The data passed to the constructor is ignored; remove it.

• Can you come up with more readable names for arr1 and arr2? Perhaps left and right (even though that may be misleading and is still arbitrary) will be easier to read than spotting 1 vs. 2 in a name.

• In merge I think using while (j < arr1.length && k < arr2.length) instead of for is more readable. It also allows you to move the "copy the rest of the non-empty array onto the end" logic out of the loop and avoid using break.

• Don't create a result array in main before calling sort--it's thrown away immediately.

Answer 2

It seems like it should work. But you're wasting a lot of time on memory allocation: you keep creating arrays and then abandoning them. Every time you create an array (or object), the JVM spends time allocating memory for it. And, eventually, deallocating it. It's not terrible - still O(N.log(N)) time - but if you're concerned about performance then you should fix this.

The following snippet (also mentioned in David Harkness's 5th bullet point) suggests to me that you don't understand declaration and creation of arrays/objects in Java:

int res[] = new int[d.length];
res = mySort.sort(d);

Perhaps your background is in C++ or something similar. In C++, when you declare a variable of array type, the array is stored in the section of memory allocated to the current function call. (I think.) This means it is necessary to know the size of the array at the time when it is declared; you can't simply declare an array of indeterminate length. Java is different: the variable you're declaring is a reference to an array (roughly equivalent to a pointer). The array itself is stored in the heap. The reference is just a memory address, so the JVM knows exactly how much memory to allocate to it, regardless of the length of the array itself. In short, in Java you don't declare the length of an array.

The first line is both a declaration and an assignment - so your code is equivalent to this:

int[] res;                  // when calling `main`, allocate memory for a reference to an array
res = new int[d.length];    // create an array of zeroes, then store a reference to it in variable `res`
res = mySort.sort(d);       // call `sort`, then store its return value (a reference to an array) as `res`
                            // the reference to the original array is overwritten;
                            //   that array will be deallocated by the garbage collector at some point in the future.

The middle line is useless (indeed wasteful); all you need is this: int[] res = mySort.sort(d);.

That was a bit of a digression; it's not your worst example of creating arrays needlessly as it's only run once, but I thought it would be helpful to illustrate how to think in Java.

You're creating two arrays inside sort and another one in merge. These are run multiple times; overall, the number of arrays created is O(N) and their total length is O(N.log(N)). But you never need that much memory usage at any one time; it's perfectly possible to do this using just O(1) arrays of length N.

For instance, you could create another array as an instance variable in MyMergeSort and use it as a scratchpad for subsequent calculations. This wouldn't be very nice, in that I think you'd end up copying integers around more times than necessary.

If I was doing this, I'd structure it differently. First I'd do merges to get an array in which the first two elements are in order, the next two are in order, etc; then I'd sort them so that the first 4 were in order, the next 4 in order, and so on. Something like this:

// merge two sections of an array, outputting the result into another (pre-existing) array
private static void mergeOnce(int[] inArr, int inStart, int[] outArr, int outStart, int n) {
    int i;
    int j = 0; // iterate over the first subarray
    int k = 0; // iterate over the second subarray
    for (i = 0; i < 2 * n; i++) {
        if(j < n && k < n){
            if(inArr[inStart + j] < inArr[inStart + n + k]){
                outArr[outStart + i] = inArr[inStart + j];
                j++;
            }
            else{
                outArr[outStart + i] = inArr[inStart + n + k];
                k++;
            }
        }
        else{
            if(j < n){
                System.arraycopy(inArr, inStart + j, outArr, outStart + i, n-j);
                break;
            }
            else{
                System.arraycopy(inArr, inStart + n + k, outArr, outStart + i, n-k);
                break;
            }
        }
    }
}

private static void mergeAll(inArr, outArr, n) {
    for (int start = 0; start < inArr.length; start += 2 * n) {
        mergeOnce(inArr, start, outArr, start, n);
    }
}

public static void sort(int[] inArr) {
    int[] arr = java.util.Arrays.copyOf(inArr, inArr.length);
    int[] otherArr = new int[arr.length];
    for (int n = 1; n < arr.length; n *= 2) {
        mergeAll(arr, otherArr);
        // now we swap `arr` and `otherArr`.
        // Since these are references, we're just doing primitive operations, so the overhead is negligible.
        // We need `otherArr` to end up being an array of the correct length,
        // and we've got a spare one lying around so let's use it.
        int[] temp = otherArr;
        otherArr = arr;
        arr = temp;
    }
    return arr;
}

This way, you'd only actually create two arrays (first two lines of sort), which have the same length as the input array. You'd do the same things, just in a slightly different order.