0

I am trying to implement merge sort in java and I have written the code by following the algorithm given in the CLRS book. I continue to get the array out of bounds exception when I try to run the code. I honestly don't understand what mistake I am making here.

package mergesort;
public class MergeSort {

    public static void MergeSort(int [] input, int low, int high){
        if(low<high){
            int mid=(low+high)/2;
            MergeSort(input,low,mid);
            MergeSort(input,mid+1,high);
            Merge(input,low,mid,high);
        }
    }

    public static void Merge(int [] input, int p, int q, int r){

    int n1=q-p+1,n2=r-q;
    int [] L=new int[n1+1];
    int [] R=new int[n2+1];
    for(int i=1;i<=n1;i++){
        L[i]=input[p+i-1];
    }
    for(int j=1;j<=n2;j++){
        R[j]=input[q+j];
    }
    L[n1+1]=-1;
    R[n2+1]=-1;
    int i=1;
    int j=1;
    for(int k=p;k<=r;k++){
        if(L[i]<=R[j]){
            input[k]=L[i];i++;
        }
        else{
            input[k]=R[j];j++;
        }
    }
    }

    public static String arrayToString(int[]input){
        String print="";
        for(int v:input){
            print +=v + " ";
        }
    return print;
    }

    public static void main(String[] args) {

        int input[]={1122,432,13,223,653,8233,7,2210};

        System.out.println(arrayToString(input));
      MergeSort(input,0,(input.length-1));
      System.out.println(arrayToString(input));

    }
}
Improve this question
0

2 Answers 2

Reset to default
1 
int [] L=new int[n1+1];
L[n1+1]=-1; // this throws IndexOutOfBoundsException 
int [] R=new int[n2+1];
R[n2+1]=-1; // throws IndexOutOfBoundsException

You are declaring an array with n1+1 length . It means that the arrays go from 0 to n1.

Try to follow Java code conventions, methods starts with lower-case also variable names. Use declarative variables p q r is difficult to follow what they are. Code must be to be understand by human beings.

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

5 Comments

This may not be the only problem (the same thing appears in the next line R[n2+1]=-1;), but it definitely points to the source of the issue, so it gets my vote.
As you guys suggested, I changed it to L[n1]=-1; R[n2]=-1; Still hasn't solved the issue though.
in what line do you have IndexOutOfBoundsException
if(L[i]<=R[j]) ..this is the line
@user2793700 you are doing i++ and it's bigger than L.length do you know how to debug it?
0

The Merge algorithm in CLRS assume arrays are 1-based. However, arrays in Java are 0-based.

When I faces this kinds of issue, I may do one of the following thing.

  1. Allocate one more element for each array and discard the first element. Like this:

    int[] L = new int[n1 + 1 + 1]; // extra `+1`
int[] R = new int[n2 + 1 + 1]; // extra `+1`
// ...
int[] input = { 0, 1122, 432, 13, 223, 653, 8233, 7, 2210 }; // leading 0
MergeSort(input, 1, input.length - 1);

  2. Add -1 to each array access. Like this:

    for(int i = 1; i <= n1; i++){
    L[i] = input[p + i - 1 - 1]; // extra `-1`
}
// ...
MergeSort(input, 1, input.length);
  3. Fully understand the algorithm. No tricks. This is the suggested approach.
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.