having problems with mergesort algorithm

Question

I am currently trying to transcribe a mergesort algorithm from a pseudocode level to a working implementation in java. This is my code

public int[] merge(int a[], int b[]) {
        int c[] = new int[a.length + b.length];
        int i = 0, j = 0;
        for (int k = 0; k < c.length; k++) {
            if (a[i] <= b[j]) {
                c[k] = a[i++];
            } else {
                c[k] = b[j++];
            }
        }
        return c;
    }

The pseudocode interpretation is correct to the best of my knowledge but it keeps returning an ArrayOutofBound Exception. Where did I get it all wrong.

Consider what happens when a[a.length-1] < b[0]: you run through the entire a array, increment i to a.length, and then try to compare a non-existent element in a with the first element of b. You need to actively check for the end of one array, and then just run through the other once that happens. — dlev
– dlev, Commented Mar 20, 2012 at 2:14
@dlev is right about the cause, though it's not an edge case at all. No matter what happens, you will finish with one array before the other, and when that happens you need to be able to finish filling from the other array. — Mark Peters
– Mark Peters, Commented Mar 20, 2012 at 2:20
@MarkPeters Indeed, I did not mean to imply it was an edge case. I was just trying to use an "extreme" example to illustrate the point. — dlev
– dlev, Commented Mar 20, 2012 at 2:31

Lee Taylor · Accepted Answer · 2012-12-26 14:16:39Z

2

This would obviously give the out of bound exception because you are not keeping track of the length of a and b arrays . Since k = a + b , a and b will always be less than k . Hence the exception.

And when you apply this check, remember to copy the remaining of the items, whether they are of a[] or b[] , to copy them to c[]. See this -

for(;i<a.length;i++)
    c[k++] = a[i++];

for(;j<b.length;b++)
    c[k++] = b[j++];

edited Dec 26, 2012 at 14:16

Lee Taylor

7,99416 gold badges38 silver badges53 bronze badges

answered Dec 26, 2012 at 13:47

rknife

3002 silver badges15 bronze badges

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

Comments

Óscar López · Accepted Answer · 2012-03-20 02:43:08Z

The merge algorithm in the way you intend to implement it is a bit more elaborated, below you'll find a correct implementation:

public int[] merge(int a[], int b[]) {

    int i = 0, j = 0, k = 0;
    int m = a.length, n = b.length;
    int[] c = new int[m + n];

    // Merge to the end of one of the source arrays
    while (i < m && j < n) {
        if (a[i] <= b[j]) {
            c[k] = a[i];
            i++;
        } else {
            c[k] = b[j];
            j++;
        }
        k++;
    }

    // Determine which source array has elements remaining and
    // append those to the result array
    if (i < m) {
        for (int p = i; p < m; p++) {
            c[k] = a[p];
            k++;
        }
    } else {
        for (int p = j; p < n; p++) {
            c[k] = b[p];
            k++;
        }
    }

    return c;

}

Collectives™ on Stack Overflow

having problems with mergesort algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related