CODEWITHSUNDEEP
javaalgorithmmergesort
Siddharth Bhardwaj
Siddharth Bhardwaj

Reputation: 141

Array Index Out of Bounds Exception Merge Sort Procedure Java

I was implementing this merge sort procedure but it's throwing out of bounds exception and i can't figure why it's doing so I checked all the array parameters are satisfied but its still having the problem. 

    public class MergeSort 
    {
    public static void main(String[] args) throws ArrayIndexOutOfBoundsException
        {

        int a[]={2,4,5,7,1,2,3,6};

        System.out.println("Unsorted Array");
        for(int i=0;i<a.length;i++)
            {
            System.out.print(a[i]+" ");
            }
        try{
        MergeSort m=new MergeSort();
        a=m.merge(a, 0, 3, 7);
        }
        catch(Exception e )
        {
            e.printStackTrace();
        }
        System.out.println("\nSorted Array");
        for(int i=0;i<a.length;i++)
            {
            System.out.print(a[i]+" ");
            }


        }

    int [] merge(int a[],int p,int q,int r)
        {
        //int a[]={2,4,5,7,1,2,3,6};
        int n1=r-p+1;
        int n2=r-q;

        int L[]=new int[n1+1];
        int R[]=new int[n2+1];



        for(int i=0;i<n1;i++)
        {
            L[i]=a[i];
        }
        q=q+1;
        for(int i=0;i<n2-1;i++)
        {
            R[i]=a[q+i];
        }

        //L[n1+1]=9;
        ///R[n2+1]=9;

        int i=0,j=0;

        for(int k=0;k<r;k++)
        {
            if(L[i]<=R[j])
            {
                a[k]=L[i];
                i++;
            }
            else
            {
                a[k]=R[j];
                j++;
            }
        }




        return a;
        }
    }

Unsorted Array
2 4 5 7 1 2 3 6 java.lang.ArrayIndexOutOfBoundsException: 5
    at scom.id.MergeSort.merge(MergeSort.java:63)
    at scom.id.MergeSort.main(MergeSort.java:20)

Sorted Array
1 2 2 3 0 0 3 6

Upvotes: 0

Views: 819

Answers (3)

Kuri
Kuri

Reputation: 111

I made some modifications to your code to make it work. Here you have it:

public class MergeSort {
  public static void main(String[] args) throws ArrayIndexOutOfBoundsException{

     int a[]={2,4,5,7,1,2,3,6};

     System.out.println("Unsorted Array");
     for(int i=0;i<a.length;i++){
        System.out.print(a[i]+" ");
     }
     try{
        MergeSort m=new MergeSort();
        a=m.merge(a, 0, 3, 7);
     }catch(Exception e ){
        e.printStackTrace();
     }
     System.out.println("\nSorted Array");
     for(int i=0;i<a.length;i++){
        System.out.print(a[i]+" ");
     }
  }

  int [] merge(int a[],int p,int q,int r){
  //int a[]={2,4,5,7,1,2,3,6};
  int n1=q-p+2;
  int n2=r-q+1;

  int L[]=new int[n1];
  int R[]=new int[n2];

  for(int i=0;i<n1 -1;i++){
    L[i]=a[p+i];
  }
  L[n1 -1] = Integer.MAX_VALUE;
  //q=q+1;
  for(int i=0;i<n2 -1;i++){
    R[i]=a[q+i+1];
  }
  R[n2-1] = Integer.MAX_VALUE;

  //L[n1+1]=9;
  ///R[n2+1]=9;

  int i=0,j=0;

  for(int k = p; k <= r; k++){
      if(L[i] <= R[j]){
        a[k] = L[i++];
    }else{
        a[k] = R[j++];
    }
  }
  return a;
 }
}

Upvotes: 1

swapnil
swapnil

Reputation: 230

I did few changes for merging two left and right arrays in one single array of sorted element.Here is the solution which is running properly. Hope this will help you understand what is going wrong.

public class MergeSort {
public static void main(String[] args) throws ArrayIndexOutOfBoundsException {

    int a[] = {2, 4, 5, 7, 1, 2, 3, 6};
    System.out.println("Unsorted Array");
    for (int i = 0; i < a.length; i++) {
        System.out.print(a[i] + " ");
    }
    MergeSort m = new MergeSort();
    a = m.merge(a, 0, 3, 7);
    System.out.println("\nSorted Array");
    for (int i = 0; i < a.length; i++) {
        System.out.print(a[i] + " ");
    }
}

int[] merge(int a[], int p, int q, int r) {
    //int a[]={2,4,5,7,1,2,3,6};
    int n1 = q - p + 1;
    int n2 = r - q;

    int L[] = new int[n1];
    int R[] = new int[n2];


    for (int i = 0; i < n1; i++) {
        L[i] = a[i];
    }
    for (int i = 0; i < n2; i++) {
        R[i] = a[q + i + 1];
    }

    //L[n1+1]=9;
    ///R[n2+1]=9;

    int i = 0, j = 0 , k = 0;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            a[k] = L[i];
            i++;
        }
        else {
            a[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        a[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        a[k] = R[j];
        j++;
        k++;
    }

    return a;
   }
}

First thing wrong is array sizes that are allocated for left and right array to hold temporarily.

Upvotes: 0

Austin
Austin

Reputation: 756

line 51 needs to be for(int k=0;k<r-1;k++) that got it to work for me

Upvotes: 0

Related Questions