I implemented this merge sort algorithm into java and it didn't work

Question

This my introductory course to Algorithms, and I understand algorithms and I can design them, but this is the first time I tryed to apply it in java code, please tell me what i did wrong in this code for it to not work properly I'm trying to apply this algorithm , this is the rest of the algorithm

This is my main void:

int[] A = { 5, 2, 4, 7, 1, 3, 2, 6 };
int p = 1;
int r = A.length;

Main obi = new Main ();
obi.mergeSort (A, p, r);

my first function:

public void mergeSort (int[]A, int p, int r) {

    if (p < r){
        int q = (p + r) / 2;
        mergeSort (A, p, q);
        mergeSort (A, q + 1, r);
        merge (A, p, q, r);
    }

}

my second function:

public void merge (int[]A, int p, int q, int r) {

    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[p + i - 1];
        
    }
    
    for (int j = 0; j < n2; j++){
        R[j] = A[q + j];
        
    }
    
    int i = 0;
    int j = 0;

    for (int k = p - 1; k < r; k++){
        if (L[i] <= R[j]){
            A[k] = L[i];
            i = i + 1;
            
        } else {
            A[k] = R[j];
            j = j + 1;
            
        }
    }

}

And this is the error message I got:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1
    at Main.merge(Main.java:44)
    at Main.mergeSort(Main.java:19)
    at Main.mergeSort(Main.java:17)
    at Main.mergeSort(Main.java:17)
    at Main.main(Main.java:10)

I tried to let L[] and R[] have length n1+1 and n2+1 but it didn't help.

Answer 1

There are multiple problems in your code:

• the arguments r and q should be the index of the first element in the slice, hence int p = 0; in main() instead of 1, and the index past the last element in the slice, hence correctly int r = A.length;

With this convention, there is no need for confusing and error prone +1/-1 adjustments in the merge and mergeSort methods.

Furthermore, the merging loop in merge should be modified to avoid accessing L[i] or R[j] when the corresponding index reaches the length of the array.

Here is a modified version:

    ...
    int[] A = { 5, 2, 4, 7, 1, 3, 2, 6 };
    int p = 0;
    int r = A.length;

    Main obi = new Main();
    obi.mergeSort(A, p, r);
    ...

public void mergeSort(int[]A, int p, int r) {
    if (r - p > 1) {
        int q = p + (r - p) / 2;
        mergeSort(A, p, q);
        mergeSort(A, q, r);
        merge(A, p, q, r);
    }
}

public void merge(int[]A, int p, int q, int r) {
    int n1 = q - p;
    int n2 = r - q;

    int L[] = new int[n1];
    int R[] = new int[n2];

    for (int i = 0; i < n1; i++) {
        L[i] = A[p + i];
    }
    
    for (int j = 0; j < n2; j++) {
        R[j] = A[q + j];
    }
    
    int i = 0;
    int j = 0;

    for (int k = p; k < r; k++) {
        if (i < n1 && (j >= n2 || L[i] <= R[j])) {
            A[k] = L[i];
            i = i + 1;
        } else {
            A[k] = R[j];
            j = j + 1;
        }
    }
}

Note that the merge method can be simplified as the elements of the second half never get overwritten before they are moved into their final spot, so there is no need to save them:

public void merge(int[]A, int p, int q, int r) {
    int n1 = q - p;
    int L[] = new int[n1];
    for (int i = 0; i < n1; i++) {
        L[i] = A[p + i];
    }
    
    int i = 0;
    int j = q;
    int k = p;

    while (i < n1) {
        if (j >= r || L[i] <= A[j])
            A[k++] = L[i++];
        else
            A[k++] = A[j++];
    }
}