CODEWITHSUNDEEP
javamergesort
user2793700
user2793700

Reputation:

arrayoutofbounds exception - Merge sort (CLRS)

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));

    }
}

Upvotes: 0

Views: 404

Answers (2)

johnchen902
johnchen902

Reputation: 9609

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.

Upvotes: 0

nachokk
nachokk

Reputation: 14413

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.

Upvotes: 1

Related Questions