CODEWITHSUNDEEP
javaarraysalgorithmindexoutofboundsexceptionmergesort
Ashish Verma
Ashish Verma

Reputation: 31

My merge sort program shows an array out of bound in Java

I'm learning Java and I make this merge sort program but it throws an Exception of ArrayOutOfBound. What is my mistake?

I also use this code at array.length or array.length-1 but both the cases are failed. It seems my code is not accepting the array's length.

// To divide the array---

void divide(int a[], int lb, int ub) {
    if (lb < ub) {
        int mid = (lb + ub) / 2;
        divide(a, lb, mid);
        divide(a, mid + 1, ub);
        merge(a, lb, mid, ub);
    }
}

//For printing the actual array---

static void ActualArray(int a[]) {
    System.out.println("----!!!Merge Sort!!!----");
    System.out.println("Your Array is: ");
    for (int i : a) {
        System.out.print(i + " ");
    }
    System.out.println("\n");
}

//For merging the Array

void merge(int a[], int lb, int mid, int ub) {
    int i = lb;
    int j = mid + 1;
    int k = lb;
    int b[] = {};
    while (i <= mid && j <= ub) {
        if (a[i] < a[j]) {
            b[k] = a[i];
            i++;
        } else {
            b[k] = a[j];
            j++;
        }
        k++;
    }
    if (i > mid) {
        while (j <= ub) {
            b[k] = a[j];
            j++;
            k++;
        }
    } else {
        while (i <= mid) {
            b[k] = a[i];
            i++;
            k++;
        }
    }
    System.out.println("Your Sorted Array is: ");
    for (int ele : b) {
        System.out.print(ele + " ");
    }
}

// Main Method

public static void main(String args[]) {
    int arr[] = { 25, 16, 45, 17, 84, 61 };
    ActualArray(arr);

    MergeSort obj = new MergeSort();
    obj.divide(arr, 0, arr.length - 1);
}

Error Image

Upvotes: 2

Views: 161

Answers (1)

chqrlie
chqrlie

Reputation: 144685

There are multiple problems in your merge method:

  • you do not allocate the temporary array b. You should write int b[] = new int[ub - lb + 1];
  • the index k into the temporary array should be initialized to 0, not lb.
  • you should copy the contents of the temporary array back to a.
  • printing the sorted slice is for debugging only.

Here is a modified version:

void merge(int a[], int lb, int mid, int ub) {
    int b[] = new int[ub - lb + 1];
    int i = lb;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= ub) {
        if (a[i] < a[j]) {
            b[k++] = a[i++];
        } else {
            b[k++] = a[j++];
        }
    }
    // copy the remaining elements from the left part
    while (i <= mid) {
        b[k++] = a[i++];
    }
    // the remaining elements from the right part are already in the proper place
    // copy back the sorted slice into the original array
    for (i = 0; i < k; i++) {
        a[lb + i] = b[i];
    }
}

Upvotes: 1

Related Questions