0

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.

Kick Buttowski
  • 6,709
  • 13
  • 37
  • 58
redeagle47
  • 1,355
  • 4
  • 14
  • 26

1 Answers1

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.

Adrian Leonhard
  • 7,040
  • 2
  • 24
  • 38
  • okay, this is great. Thanks for the help, I didn't see the second for loop starting at 0. For the first edit, I thought I would need to start the right half with an offset mid because left had already taken the mid as it's last element. For the second edit, creating the arrays in line like that is exactly what I've been trying to figure out for the past couple hours, so thanks ( I mean how to use the b[0] as an array, not the syntax). – redeagle47 Mar 24 '15 at 22:05
  • Actually, could you explain what you mean about not using merge as a bad concat? – redeagle47 Mar 24 '15 at 22:20
  • 1
    Well, it only works as a concat if one of the arrays has a length of 1. Also, the functionality doesn't really belong in merge. If you want to use concat as in the example you referenced in the question, you should define it in a separate function. See http://stackoverflow.com/questions/80476/how-to-concatenate-two-arrays-in-java for an implementation. – Adrian Leonhard Mar 24 '15 at 23:28
  • okay, that makes sense. I added that in because of the problem with IndexOutOfBoundsExceptions, the part about the length of 1 arrays I mean. Thanks for all the help. – redeagle47 Mar 25 '15 at 02:30