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 + " ");
        }
    }
}

Apart from your primary problem (which I've explained in the answer) you also overwrite result with a new int[] when you should really just write the result to the array passed in (i.e. get rid of the line result = new int[L.length + R.length];). — Joachim Sauer
– Joachim Sauer, Commented Jan 6, 2021 at 18:51
@ShantanuStudyCircle: You can accept one of the answers by clicking on the grey checkmark below its score. — chqrlie
– chqrlie, Commented Jan 30, 2021 at 11:52

Joachim Sauer · Accepted Answer · 2021-01-06 18:50:16Z

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.

answered Jan 6, 2021 at 18:50

Joachim Sauer

309k59 gold badges568 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

chqrlie · Accepted Answer · 2021-01-06 19:23:06Z

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

Collectives™ on Stack Overflow

Getting StackOverFlow error while trying to code Merge Sort in Java

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related