Recursive Merge Sort - Stack Overflow Error

Question

I'm doing a school project where I have to write a program that performs a merge sort. The mergeSort() method is recursive and is causing a stack overflow error. I know that this happens if a recursive method continues endlessly, but I can't figure out what in my code is making it not stop.

Any help would be greatly appreciated.

Here is the code (it's run with a Sort.java program provided by my professor, if that clarifies why there is no main method):

public class Merge {

    /**
     * Sort an array, in-place, using merging.
     * @param array The array to be sorted.
     * POSTCONDITION: The elements of array are in ascending order.
     */
    public static void sort(int[] array) {

        int[] tempArray = mergeSort(array);
        for (int i = 0; i < tempArray.length; i++) {
            array[i] = tempArray[i];
        }
    }

    /**
     * Extract the portion of an array from start up to (excluding) stop.
     * @param array The source array.
     * @param start The starting index (inclusive).
     * @param stop  The ending index (exclusive).
     * @return An array containing the same elements the portion of array.
     * PRECONDITION: 0 <= start <= stop <= array.length
     */
    private static int[] subarray(int[] array, int start, int stop) {

        int[] newArray = new int[stop-start];
        for (int i = 0; i < newArray.length; i++) {
            newArray[i] = array[start + i];
        }
        return newArray;
    }

    /**
     * Merge two sorted arrays into one new array.
     * @param first The first array, already sorted.
     * @param second The second array, already sorted.
     * @return A new array containing the elements of first and second,
     *         in order.
     */
    private static int[] merge(int[] first, int[] second) {

        int[] newArray = new int[first.length + second.length]; 
        int count = 0;
        int i = 0;
        int j = 0;
        while ((i < first.length) || (j < second.length)) {
            if ((i < first.length) && (j < second.length)) {
                if (first[i] < second[j]) {
                    newArray[count++] = first[i++];
                } else { 
                    newArray[count++] = second[j++];
                }
            } else if (j < second.length) {
                newArray[count++] = second[j++]; 
            } else if (i < first.length) { 
                newArray[count++] = first[i++];
            }
        }
        return newArray;
    }

    /**
     * Sort an array by merging.
     * @param array The array to sort.
     * @return A new array containing the elements of array, in order.
     */
    private static int[] mergeSort(int[] array) {
        int split = 0;
        if (array.length < 2) {
            return array;
        } else {
            split = array.length%2;
            int[] array1 = mergeSort(subarray(array, 0, split));
            int[] array2 = mergeSort(subarray(array, split, array.length));
            return merge(array1, array2);
        }
    }  
}

Answer 1

I assume split = array.length%2; is supposed to be split = array.length/2;

It's going to take a while if the array has an even length, since the second subarray will effectively be equal to the original array, and you get infinite recursion. With an odd-length array, the second subarray will be even-length, and you again get infinite recursion.

---

To debug infinite recursion, first use printf statements to check what's going on just before you recurse (since that'll probably be where things go wrong) to make sure the recursion is going as planned, like:

split = array.length%2;
System.err.printf(
    "%d broken into %d (%d to just before %d) and %d (%d to just before %d).\n",
    array.length, split, 0, split, array.length - split, split, array.length);
int[] array1 = mergeSort(subarray(array, 0, split));
int[] array2 = mergeSort(subarray(array, split, array.length));
return merge(array1, array2);

See if things are getting smaller in the ways that they should.