Array Index Out of Bounds Exception Merge Sort Procedure Java

Question

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

What is the exact error message, and what line is causing it? Edit question and show us the full stacktrace, and since we can't see line numbers, tell us which line it is. — Andreas
– Andreas, Commented Nov 26, 2016 at 17:05
@JamesKPolk Please do not apply your personal code style to other peoples questions/answers. OP's code style was to have { on separate lines. That is a perfectly valid code style. Undo'ing edit. — Andreas
– Andreas, Commented Nov 26, 2016 at 17:11
@Andreas the line's are a=m.merge(a, 0, 3, 7); and if(L[i]<=R[j]) — Siddharth Bhardwaj
– Siddharth Bhardwaj, Commented Nov 26, 2016 at 17:40

Kuri · Accepted Answer · 2016-11-26 18:51:14Z

1

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

edited Nov 26, 2016 at 18:51

answered Nov 26, 2016 at 18:16

Kuri

1111 silver badge11 bronze badges

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

3 Comments

Siddharth Bhardwaj Over a year ago

7 is missing from result.

Siddharth Bhardwaj Over a year ago

Could you pleas explain why we are putting L[n1-1]=Integer.Max_Value ;and R[n2-1] = Integer.MAX_VALUE;

Kuri Over a year ago

It is a reference to know that we've reached the end of the array. The idea is to add an "infinite" value at the end, so when we reach this value, the algorithm will only copy the values of the other array because we guarantee that they are going to be lower. Another way to achieve this would be to check in each iteration if one of the arrays to merge has reached its last index, and then just copy the other one, but if both arrays have similar sizes, this would imply a lot of unnecesary comparisons.

Austin · Accepted Answer · 2016-11-26 17:10:15Z

0

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

answered Nov 26, 2016 at 17:10

Austin

7564 silver badges24 bronze badges

3 Comments

Andreas Over a year ago

Really? Unsorted Array: 2 4 5 7 1 2 3 6, Sorted Array: 1 2 2 3 0 0 3 6. Does that "work for you"? Because it sure doesn't look like the right output to me.

Siddharth Bhardwaj Over a year ago

@Austin but it has to be sorted as well,is there's something wrong with merge algorithm i am using.

Austin Over a year ago

it's very hard for me to understand your code unless you can tell me what the different variables mean.

swapnil · Accepted Answer · 2016-11-26 17:58:18Z

0

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.

answered Nov 26, 2016 at 17:58

swapnil

2303 silver badges6 bronze badges

3 Comments

Siddharth Bhardwaj Over a year ago

your solution is working fine , but what is wrong with my code is my primary concern.

swapnil Over a year ago

So first thing is that

swapnil Over a year ago

int n1=r-p+1; is Wrong. It should be n1 = q-p+1; Which represents the size of left array. k<r is wrong it should be k <= r.Also their should be conditions on i and j as i < n1 and j < n2. So you will not not exceed array size of left and right array.

Collectives™ on Stack Overflow

Array Index Out of Bounds Exception Merge Sort Procedure Java

3 Answers 3

3 Comments

3 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

3 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related