Mergesort Array Index out of bounds exception

Question

package merge;
public class Merger {   
int[] a = {1, 10, 5, 9};
// int[] a = {1, 10, 5, 9, 8, 6, 3, 2};
public Merger(){        
    mergSort(a,0,3);        
    for(int i =0; i<a.length;i++){
        //System.out.println(a[i]);
    }
}

private void mergSort(int[] a, int l, int r) {
    if(l>=r){
        return;
    }
    int m=(l+r)/2;      
    mergSort(a,l,m);
    mergSort(a,m+1,r);      
    merge(a,l,m,r);     
}

private void merge(int[] a, int l, int m, int r) {
    int p = l;
    int u = l;
    int v = m + 1;
    int n = (r-l) + 1;
    int[] result = new int[n];
    int s = 0;

    while(p <= r){
        if(u>v){
            s = a[v];
            v = v + 1;
        } else if (v>r){
            s = a[u];
            u = u + 1;
        } else {
            if(a[u]<a[v]){
                s = a[u];
                u = u + 1;
            } else {
                s = a[v];
                v = v + 1;
            }
        }
        result[p] = s;
        p = p + 1;
    }
    copy(result, a, l, r);      
}

private void copy(int[] result, int[] a, int l, int r) {
    for(int i = l; i <= r; i++){
        a[i] = result[i];
    }
}

public static void main(String[] args) {
    Merger m = new Merger();
}

}

I keep throwing an ArrayIndexOutOfBoundsException at the line result[p] = s. I think it may have something to do with the final merge, but I am not sure. When i hard code the size of the result array to be the size of array a, my program works. I am not sure what is happening. I would appreciate any help

cyon · Accepted Answer · 2013-09-26 23:42:23Z

1

The result array is the right size, but you don't index it correctly. You use l as the start index, but the array's first available spot is at 0 and l may be larger than zero. You need to subtract l from p for the indexing to work.

result[p-l] = s;

And

for(int i = l; i <= r; i++){
    a[i] = result[i-l];
}

edited Sep 26, 2013 at 23:42

answered Sep 26, 2013 at 23:36

cyon

9,5684 gold badges24 silver badges26 bronze badges

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

Collectives™ on Stack Overflow

Mergesort Array Index out of bounds exception

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related