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.

I think it should be int[] right = Arrays.copyOfRange(a,mid + 1,a.length-1); because the last element of a 0 based array is length-1. — martinstoeckli
– martinstoeckli, Commented Mar 24, 2015 at 21:08
@AdrianLeonhard - I see, i'm not familiar with Java so i thought it would be similar to C#. — martinstoeckli
– martinstoeckli, Commented Mar 24, 2015 at 21:12

Adrian Leonhard · Accepted Answer · 2015-03-24 21:26:25Z

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.

edited Mar 24, 2015 at 21:26

answered Mar 24, 2015 at 21:19

Adrian Leonhard

7,4503 gold badges27 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

redeagle47 Over a year ago

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 Over a year ago

Actually, could you explain what you mean about not using merge as a bad concat?

Adrian Leonhard Over a year ago

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 stackoverflow.com/questions/80476/… for an implementation.

redeagle47 Over a year ago

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.

Collectives™ on Stack Overflow

merge function of merge sort algorithm logic is wrong

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related