Search code examples
javamergesort

Trying to do the mergeSort, and the index out of bounds


I'm trying to do the mergeSort. and when I run the test. It said my index is out of bounds. Is there any mistake I missed?

Error is: java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3

public static void mergeSort(int[] a) {
    int[] L = null; 
    int[] R = null; 

    if (a.length < 2)
        return;
    L = new int[a.length / 2];
    R = new int[a.length - a.length / 2];
    int x = 0;
    for (int y = 0; y < a.length; y++) {
        if (y < a.length) {
            L[y] = a[y];
        } else {
            R[x] = a[y];
            x += 1;
        }
    }
    mergeSort(L);
    mergeSort(R);
    merge(a, L, R); 
}

public static void merge(int[] a, int[] L, int[] R) {
    tracker.calltracking(a, L, R);
    int x = 0, y = 0, z = 0;
    while (x < L.length && y < R.length) {
        if (L[x] < R[y]) {
            a[z++] = L[x++];
        } else {
            a[z++] = R[y++];
        }
    }
    while (x < L.length) {
        a[z++] = L[x++];
    }
    while (z < R.length) {
        a[z++] = R[y++];
    }
}

Solution

  • Let's debug the mergeSort method with a of length 3.

    L is initialized with size of 1, and R with size of 2

    You will enter the loop.

    First iteration: y is 0, y is less than a.length

    Second iteration: y is 1, y is less than a.length. Oops! L in index 1 is OutOfBounds.