0

Here is my merge procedure which I am calling within this function:

public static void mergeSort(int[] a, int l, int r){
        if (l <r){      
    int m = (int)((l+r)/2.0);
    mergeSort(a, l, m);
    mergeSort(a, m+1, r);
    merge(a, l, m,r);
    } 
 }

private static void merge(int[] a, int l, int m, int r){

    int[] b = new int[a.length];
    int h;
    int i = l;
    int j = m+1;
    int k = l;
    while( (i <= m) && (j <= r)){
        if(a[i] <= a[j]){
            //a[i] --> b[k]
            b[k] = a[i];
              i = i+1;
    } else {
            //a[j] --> b[k]
            b[k] = a[j];
               j = j+1;
      }
        k = k+1;
    }
 // Now add any remaining elements from both halves
if (i > m) {
    for (h=j; h< r; h++){
        b[k+h-j] = a[h];
    }
} else {
    //take 2nd sequence
    for (h=i; h< m; h++){
        b[k+h-i] = a[h];
    }   
}

//copy back into a 
for (h= k; h< r; h++){
    a[h] = b[h];
  }
 }

The array looks like this: 4 3 3 5 1 2 7 12

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 8

i.e. getting an out of bounds on the upper bound r

Can anyone see the bug? - been driving me crazy...

SOLUTION UPDATE Need to make sure the mergeSort method is called with the correct params initially. That wasn't specified in the original textbook algorithm - thank you Prof. PW!! Very thorough work!

As the commenter suggests calling mergeSort(int[], 0, length-1) is required

Mathflunkie
  • 13
  • 3

1 Answers1

1

The reason for your failure is that you are not passing the correct values to the mergeSort method. For example, the following call will generate the error that you have mentioned:

int[] a = {4, 3, 3, 5, 1, 2, 7, 12};
mergeSort(a, 0, 8);

The reason is that the value of r must be 7 and not the length of the array. The following code will not cause any error:

int[] a = {4, 3, 3, 5, 1, 2, 7, 12};
mergeSort(a, 0, 7);
Sarangan Rajamanickam
  • 63
  • 3