Getting StackOverFlow error while trying to code Merge Sort in Java

Question

I am new to coding and I was trying to create merge sort algorithm in java. I am getting too many errors and I am not able to figure out the exact mistake in the code. I feel my logic is correct but don't know which step(s) is causing the error. Could someone help me rectify the mistakes in the following code. Thank you

package com.company;
public class MergeSort_Array {
    //Method created to print Input Array
    public static void printInputArray(int inputArray[]) {
        for (int i:inputArray) { //for-each loop
            System.out.print(i + " ");
        }
        System.out.println();
    }

    //Function created to sort and merge Input Array:
    public static void SortArray(int[] A) {
        int midpoint = A.length / 2;
        int[] left = new int[midpoint];
        int[] right;
        if (A.length % 2 == 0) {
            right = new int[midpoint];
        } else {
            right = new int[midpoint + 1];
        }
        //Copying values from super Array to left Array:
        for (int i = 0; i < midpoint; i++) {
            left[i] = A[i];
        }
        //Copying elements from super Array to right Array:
        for (int j = 0; j < right.length; j++) {
            right[j] = A[midpoint + j];
        }
        //using Recursion
        SortArray(left);
        SortArray(right);
        MergeArray(A, left, right);
    }

    // Creating a Function to merge left and right arrays.
    public static void MergeArray(int[] result, int[] L, int[] R) {
        //result array length = length of left array+ right array length
        result = new int[L.length + R.length];
        int i = 0, j = 0, k = 0;
        while (k < result.length) {
            if (L[i] < R[j]) {
                result[k] = L[i];
                i++;
            } else
            if (R[j] < L[i]) {
                result[k] = R[j];
                j++;
            } else
            if (i > L.length) {
                while (j <= R.length) {
                    result[k] = R[j];
                    j++;
                }
            } else
            if (j > R.length && i <= L.length) {
                while (i <= L.length) {
                    result[k] = L[i];
                    i++;
                }
            }
            k++;
        }
    }

    public static void main(String[] args) {
        int[] inputArray = { 2, 5, 4, 1, 7, 9, 6 };
        MergeSort_Array ms = new MergeSort_Array();
        ms.printInputArray(inputArray);
        SortArray(inputArray);

        for (int i: inputArray) {
            System.out.println(i + " ");
        }
    }
}

Answer 1

There are multiple problems in your code:

• [Major] SortArray() always attempts to split the array and sort both halves. You should not do this if the array length is less than 2, otherwise you get an infinite recursion causing a stack overflow exception.

• [Hint] right can be initialized unconditionally as int[] right = new int[A.length - midpoint];

• [Major] MergeArray should not reallocate the destination array. The merge must be performed in place into result so the caller's object is updated.

• [Major] in the merge loop, you must test the index values before attempting to read L[i] or R[j], otherwise you might get an out of bounds exception.

Here is a modified version:

package com.company;
public class MergeSort_Array {
    // Method created to print Input Array
    public static void printInputArray(int inputArray[]) {
        for (int i : inputArray) { //for-each loop
            System.out.print(i + " ");
        }
        System.out.println();
    }

    //Function created to sort and merge Input Array:
    public static void SortArray(int[] A) {
        if (A.length >= 2) {
            int midpoint = A.length / 2;
            int[] left = new int[midpoint];
            int[] right = new int[A.length - midpoint];

            //Copying values from super Array to left Array:
            for (int i = 0; i < midpoint; i++) {
                left[i] = A[i];
            }
            //Copying elements from super Array to right Array:
            for (int j = 0; j < right.length; j++) {
                right[j] = A[midpoint + j];
            }
            //using Recursion
            SortArray(left);
            SortArray(right);
            MergeArray(A, left, right);
        }
    }

    // Creating a Function to merge left and right arrays.
    public static void MergeArray(int[] result, int[] L, int[] R) {
        for (int i = 0, j = 0, k = 0; k < result.length; k++) {
            if (j >= R.length || (i < L.length && L[i] < R[j])) {
                result[k] = L[i++];
            } else {
                result[k] = R[j++];
            }
        }
    }

    public static void main(String[] args) {
        int[] inputArray = { 2, 5, 4, 1, 7, 9, 6 };
        printInputArray(inputArray);
        SortArray(inputArray);
        printInputArray(inputArray);
    }
}

Answer 2

Every time you call SortArray it will itself call SortArray twice. There is no end condition: every invocation will try to call SortArray twice.

This means that no call of SortArray can ever complete, since you infinitely recurse in each of them.

There must be some base case where it no longer calls itself. For mergesort one usually switches to some other algorithm once the array is small enough, but for simplicities sake you can even fall back to the most trivial base case for sorting: any array shorter than 2 elements is always sorted and needs nothing else to be done to be sorted.