1

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);
        }
    }  
}
4
  • 3
    Java is to Javascript as Pain is to Painting, or Ham is to Hampster. They are completely different. It is highly recommended that aspiring coders try to learn the name of the language they're attempting to write code in. When you post a question, please tag it appropriately. Commented Oct 17, 2018 at 2:55
  • 1
    @CertainPerformance Actually, there is a reason why JavaScript bears its name. There originally was a relation between Java and JavaScript; the latter was intended to be used to control Java applets running in early web pages. But yeah, for sure they're not the same language. Commented Oct 17, 2018 at 2:57
  • 1
    This is a good time for you to learn how to use a debugger. Get into your code, line by line, and see what is happening. Start with small input arrays, say of size 4 or less. So my answer is: use a debugger. Commented Oct 17, 2018 at 2:58
  • one thing: the implementations of mergesort i checked all don't modulo split = array.length%2; but split = array.length/2; as pointed out by a user who just deleted his comment. Commented Oct 17, 2018 at 3:18

1 Answer 1

3

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.

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.