merge sort stack overflow error

Question

I'm writing a merge sort function, but can't get past this stack overflow error at line 15, line 16 of my code which is where the recursive call happens.

public class MergeSort {

     private int [] tempArray;



    public void mSort(int [] A, int low, int high)
    {
        if(high-low >1)
        {
            mSort(A, low, (high/2));  **Line 15 ERROR**
            mSort(A, ((high / 2) + 1), high);**Line 16 ERROR**
            Merge(A, low, (high / 2 + 1), high);
        }

    }


    public void Merge(int [] A, int low, int mid, int high)
    {
        int length = high - low +1;
        int indexlow = low;
        int indexhigh = mid;
        int index = low;
        tempArray = new int[length];
        while(indexlow < mid || indexhigh < high)
        {
            if(indexlow >= mid)
            {

                tempArray[index] = A[indexhigh];
                index = index + 1;
                indexhigh = indexhigh + 1;
            }
            else if(indexhigh > high)
            {

                tempArray[index] = A[indexlow];
                index = index + 1;
                indexlow = indexlow +1;
            }
            else if(A[indexlow] <= A[indexhigh])
            {

                tempArray[index] = A[indexlow];
                index = index + 1;
                indexlow = indexlow + 1;
            }
            else
            {

                tempArray[index] = A[indexhigh];
                index = index + 1;
                indexhigh = indexhigh +1;
            }
        }
        for(int i = low; i <= high; i++)
        {
            A[i] = tempArray[i];
        }
    }
}

public class Main {

    public static void main(String[] args) {
    // write your code here
        int A = 7/2;
        int [] inputArray = {4, 10, 1, 5, 3, 8, 7, 6};
        MergeSort myMergeSort = new MergeSort();

        myMergeSort.mSort(inputArray, 0, inputArray.length-1);

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

can someone please help me understand what is wrong with my code? I am lost and can't comprehend. I've tried reading all over the website but still can't understand it.

Answer 1

The problem is in

if (high-low > 1) {
    mSort(A, low, (high/2));  **Line 15 ERROR**
    mSort(A, ((high / 2) + 1), high);**Line 16 ERROR**
    Merge(A, low, (high / 2 + 1), high);
}

If high = 3 and low = 2, it will cause infinite loop, so stackoverflow error will be thrown.

And please notice, when high - low == 1, you should also merge them.

Here is a working version:

public class MergeSort {

    private static int [] tempArray;

    public void mSort(int [] A, int low, int high) {
        if (high > low) {
            int mid = low + (high - low) / 2;
            mSort(A, low, mid);
            mSort(A, mid + 1, high);
            Merge(A, low, mid + 1, high);
        }
    }

    public void Merge(int [] A, int low, int mid, int high) {
        int indexlow = low;
        int indexhigh = mid;
        int index = low;
        while(indexlow < mid || indexhigh <= high) {
            if(indexlow >= mid) {
                tempArray[index] = A[indexhigh];
                indexhigh++;
            } else if(indexhigh > high) {
                tempArray[index] = A[indexlow];
                indexlow++;
            } else if(A[indexlow] <= A[indexhigh]) {
                tempArray[index] = A[indexlow];
                indexlow++;
            } else {
                tempArray[index] = A[indexhigh];
                indexhigh++;
            }
            index++;
        }
        for(int i = low; i <= high; i++) {
            A[i] = tempArray[i];
        }
    }

    public static void main(String[] args) {
        int [] inputArray = {4, 10, 1, 5, 3, 8, 7, 6};
        tempArray = new int[inputArray.length];
        MergeSort myMergeSort = new MergeSort();
        myMergeSort.mSort(inputArray, 0, inputArray.length-1);
        for(int i : inputArray) {
            System.out.print(i);
            System.out.print(" ");
        }
    }
}