I have an issue with implementing Merge Sort for Java

Question

public static void main(String[] args) {
    int[] test = {5,4,3,5,7,5,1,5,96};
    System.out.print("Before: ");
    printList(test);
    mergeSort(test, 1, test.length);
    //System.out.print("After:  ");
    //printList(test);
}

public static void printList(int[] test){
    for (int i= 0; i < test.length; i++){
        System.out.print(test[i] + " ");
    }
    System.out.println();
}

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

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

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

I am trying to implement merge sort on a test array, but I am not sure why I am getting an ArrayIndexOutOfBoundsException error on this. The assignment is to change the merge sort code to not use any sentinels when searching.

    Before: 5 4 3 5 7 5 1 5 96 
    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1
    at Lab1_2.merge(Lab1_2.java:28)
    at Lab1_2.mergeSort(Lab1_2.java:61)
    at Lab1_2.mergeSort(Lab1_2.java:59)
    at Lab1_2.mergeSort(Lab1_2.java:59)
    at Lab1_2.mergeSort(Lab1_2.java:59)
    at Lab1_2.main(Lab1_2.java:8)

This is the error message that I get.

Answer 1

A better readable solution could be

public class MergeSort {

    private int[] array;
    private int[] tempMergArr;
    private int length;

    public static void main(String a[]){

        int[] inputArr = {5,4,3,5,7,5,1,5,96};
        System.out.print("Before: ");
        printList(inputArr);
        MergeSort mms = new MergeSort();
        mms.sort(inputArr);
        System.out.print("After: ");
        printList(inputArr);
    }

    public static void printList(int[] test){
        for (int i= 0; i < test.length; i++){
            System.out.print(test[i] + " ");
        }
        System.out.println();
    }
    public void sort(int inputArr[]) {
        this.array = inputArr;
        this.length = inputArr.length;
        this.tempMergArr = new int[length];
        mergeSort(0, length - 1);
    }

    private void mergeSort(int lowerIndex, int higherIndex) {

        if (lowerIndex < higherIndex) {
            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
            // Below step sorts the left side of the array
            mergeSort(lowerIndex, middle);
            // Below step sorts the right side of the array
            mergeSort(middle + 1, higherIndex);
            // Now merge both sides
            merge(lowerIndex, middle, higherIndex);
        }
    }

    private void merge(int lowerIndex, int middle, int higherIndex) {

        for (int i = lowerIndex; i <= higherIndex; i++) {
            tempMergArr[i] = array[i];
        }
        int i = lowerIndex;
        int j = middle + 1;
        int k = lowerIndex;
        while (i <= middle && j <= higherIndex) {
            if (tempMergArr[i] <= tempMergArr[j]) {
                array[k] = tempMergArr[i];
                i++;
            } else {
                array[k] = tempMergArr[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            array[k] = tempMergArr[i];
            k++;
            i++;
        }

    }
}

Answer 2

you are getting ArrayIndexOutOfBoundsException run time exception because you are try to accessing array out of your array boundary (limits). in merge method your statements like

 int[] L = new int[n1];

you declare array of size n1 you can get element at index from 0 to n-1. but you are try to storing element at index n1. which is not possible because as we know array having element from 0 to size-1 (here size is length of array) this is one of the reason. you have issue some other places. So I edit your code and hope following code work for you.

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;


class Ideone
    {
    public static void main (String[] args) throws java.lang.Exception
    {
    // your code goes here
        int[] test = {5,4,3,5,7,5,1,5,96};
    System.out.print("Before: ");
    printList(test);
    mergeSort(test, 0, test.length-1);
    System.out.print("After:  ");
    printList(test);
}

public static void printList(int[] test){
for (int i= 0; i < test.length; i++){
    System.out.print(test[i] + " ");
}
System.out.println();
}

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

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

       int i = 0, j = 0;


    int k = p;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            A[k] = L[i];
            i++;
        }
        else
        {
            A[k] = R[j];
            j++;
        }
        k++;
    }


    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }


    while (j < n2)
    {
        A[k] = R[j];
        j++;
        k++;
    }

}

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

}

Answer 3

careful with their array indexes, change to main

   mergeSort(test,0, test.length-1); // change array init index 0