merge function of merge sort algorithm logic is wrong

Question

I am trying to implement mergesort in Java. I understand the algorithm, but am having trouble with the implementation. Here is the code I have written:

package sort;

import java.util.Arrays;

public class MergeSort {

public MergeSort() {

}

public static void main(String[] args) {

    int[] d = {26,14,72,34,622,483};
    MergeSort ms = new MergeSort();
    int[] results = ms.mergesort(d);
    for (int i = 0; i < results.length; i++) {
        System.out.println(results[i]);
    }

}

public int[] mergesort(int[] a) {

    System.out.println("Another call to merge sort");

    if (a.length <= 1) { return a;}

    int mid = a.length / 2;
    int[] left = Arrays.copyOfRange(a,0,mid);
    int[] right = Arrays.copyOfRange(a,mid + 1,a.length);

    left = mergesort(left);
    right = mergesort(right);

    int[] result = merge(left,right);
    return result;
}

private int[] merge(int[] b, int[] c) {
    System.out.println("Another call to merge");

    int[] result = new int[b.length+c.length];

    if (b.length == 0) {
        return c;
    } else if (c.length == 0) {
        return b;
    } else if (b[0] < c[0] && b.length == 1) {
        result[0] = b[0];
        for (int i = 1; i < result.length; i++) {
            result[i] = c[i -1];
        }
        return result;
    }else if (b[0] > c[0] && c.length == 1) {
        result[0] = c[0];
        for (int i = 0; i < result.length; i++) {
            result[i] = b[i-1];
        }
        return result;
    }
    else if (b[0] < c[0]) {
        result[0] = b[0];
        result = merge(result,merge(Arrays.copyOfRange(b,1,b.length),c));
        return result;
    } else if (b[0] > c[0]) {
        result[0] = c[0];
        result = merge(result,merge(b,Arrays.copyOfRange(c,1,c.length)));
        return result;
    } else {
        System.out.println("Fell to the bottom.");
        return result;
    }
}

}

The problem is my merge function. I tried to follow the algorithm here: http://discrete.gr/complexity/ but I kept getting IndexOutOfBoundsExceptions because if the array was only of size 1, there isn't an index 1 for Arrays.copyOfRange to grab. I tried to fix this in my code, but it's getting really messy. With the way it is now, it will make a lot of calls down into the functions, and then throw a IndexOutOfBoundsException. I would really appreciate some help with this. And I'm just doing this on my own to try to figure it out, not as a homework assignment.

Answer 1

I would recommend implementing merge iteratively instead of recursively. Having merge also be a bad concat function, which is used in your example, is confusing (at least move it to a separate function).

In your case, the error is here:

    for (int i = 0; i < result.length; i++) {
        result[i] = b[i-1];
    }

i needs to start from 1, otherwise i - 1 == -1 which is never a valid index.

In future, note where the exception occurs in your question, and run your program through a debugger, in this case it shows the problem immediately.

EDIT: ok, that still doesn't result in a correct program. Additional errors:

int[] right = Arrays.copyOfRange(a,mid + 1,a.length);
// needs to be "mid", not "mid + 1", read the doc on the function

EDIT2: Final lines need to be:

else if (b[0] < c[0]) {
    result = merge(new int[]{b[0]},merge(Arrays.copyOfRange(b,1,b.length),c));
    return result;
} else if (b[0] > c[0]) {
    result = merge(new int[]{c[0]},merge(b,Arrays.copyOfRange(c,1,c.length)));
    return result;
} else {

otherwise, the result gets very long.