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

Question

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

First of all: Please use actual names for your variables. This is barely readable and it´s just a simple Merge Sort. This also makes it easier for other people to help you. — Alexander Heim
– Alexander Heim, Commented Apr 15, 2020 at 8:37
@ArvindKumarAvinash: no, j <= ub is correct for this implementation. The OP follows the error prone but very common convention where the slice runs from arr[lb] to arr[ub] included. I wish teachers would stop this non-sense. — chqrlie
– chqrlie, Commented Apr 15, 2020 at 11:13
@AshishVerma: you can accept one of the answers by clicking on the grey checkmark below its score. — chqrlie
– chqrlie, Commented May 3, 2020 at 22:59

chqrlie · Accepted Answer · 2020-04-15 11:19:55Z

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

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related