merge sort algorithm implemented in java giving ArrayIndexOutOfBound Exception

Question

ive rewritten it a hundred times, i keep getting an IndexOutOfBound exception. It may be an issue if the first for loop that fills in the left array, but im not sure how to change the logic.

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 10 at mergeSortWithTwist.merge(mergeSortWithTwist.java:57)

i don't know what else to do, any help is appreciated !

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

       int n1 = q-p+1;
       int n2 = r-q;
       int[] leftHalf = new int[n1];
       int[] rightHalf = new int[n2];

       for(int i = 0; i < n1; i++)
           leftHalf[i] = inputArr[p+i-1];

       for(int i = 0; i < n2; i++)
           rightHalf[i] = inputArr[q+i];

       leftHalf[n1+1] = Integer.MAX_VALUE;
       rightHalf[n2+1] = Integer.MAX_VALUE;

       int i = 0;
       int j = 0;
   

       for(int k = 0; k < r; k++) {
           if(leftHalf[i] <= rightHalf[j]){
               inputArr[k] = leftHalf[i];
               i++;
           }
           else {
               inputArr[k] = rightHalf[j];
               j++;
           }
       }

   }

    public static void merge_sort(int[] inputArr, int p, int r) {
        if(p<r) {
            int q = (p + r) / 2;
            merge_sort(inputArr,p,q);
            merge_sort(inputArr,q+1,r);
            merge(inputArr,p,q,r);
        }
    }

Answer 1

There are several issues:

• leftHalf[n1+1] = assigns to an out of range index. leftHalf has n1 entries, so n1+1 and even n1 are out of range.

• The values n1 and n2 are determined by the size of the left and right partitions, which is fine, but as you want an extra entry for storing Integer.MAX_VALUE, you would need to allocate one more entry when defining leftHalf and rightHalf.

• The assignment leftHalf[i] = inputArr[p+i-1]; will evaluate inputArr[p-1] when i is zero, but that is an index that is outside the left partition, and could even be -1 (when p is 0), which is what your exception is complaining about. This should be inputArr[p+i]. Similarly, the next statement should assign an index that is one greater.

• The final "merge" loop starts with a wrong value for k. This k should not start at 0, but at p. Secondly, it should not stop before reaching r, but include r as well.

Here is your merge function with corrections for the above issues:

    public static void merge(int[] inputArr, int p, int q, int r) {
        int n1 = q-p+1;
        int n2 = r-q;
        int[] leftHalf = new int[n1 + 1]; // Corrected: need one extra entry
        int[] rightHalf = new int[n2 + 1]; // Corrected: need one extra entry
        for(int i = 0; i < n1; i++)
            leftHalf[i] = inputArr[p+i]; // Corrected: start at inputArr[p]
        for(int i = 0; i < n2; i++)
            rightHalf[i] = inputArr[q+1+i]; // Corrected: start at inputArr[q+1]
        leftHalf[n1] = Integer.MAX_VALUE; // Corrected: use last slot
        rightHalf[n2] = Integer.MAX_VALUE; // Corrected: use last slot
        int i = 0;
        int j = 0;
        for(int k = p; k <= r; k++) { // Corrected: start at p, end at r
            if(leftHalf[i] <= rightHalf[j]){
                inputArr[k] = leftHalf[i];
                i++;
            }
            else {
                inputArr[k] = rightHalf[j];
                j++;
            }
        }
    }

Note that all these bugs can be found by meticulous debugging: stepping through the code, setting breakpoints, inspecting variables, possibly printing them.

Using MAX_VALUE?

As noted in comments: although the use of MAX_VALUE as "stopper" value simplifies the merge part of your code a bit, this requires that the input will not have this value as actual data value. If MAX_VALUE is considered a valid data value (and why not?), you cannot really use this shortcut, and would better do it without:

    public static void merge(int[] inputArr, int p, int q, int r) {
        int n1 = q-p+1;
        int n2 = r-q;
        int[] leftHalf = new int[n1];
        int[] rightHalf = new int[n2];
        for(int i = 0; i < n1; i++)
            leftHalf[i] = inputArr[p+i];
        for(int i = 0; i < n2; i++)
            rightHalf[i] = inputArr[q+1+i];
        int i = 0;
        int j = 0;
        for(int k = p; k <= r; k++) {
            // Boundary checks instead of relying on MAX_VALUE:
            if(i < n1 && (j == n2 || leftHalf[i] <= rightHalf[j])) {
                inputArr[k] = leftHalf[i];
                i++;
            }
            else {
                inputArr[k] = rightHalf[j];
                j++;
            }
        }
    }