Mergesort: getting java.lang.StackOverflowError for 100000 numbers but not for 10000

Question

My code works fine for 10000 but not for 100000 numbers.

The error occurs at

result.add(next);
result.addAll(mergeInt(left,right));

Here's the code:

private static ArrayList<Integer> mergeSortInt(ArrayList<Integer> array)
    {
        if (array.size() <= 1) return array;

        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right = new ArrayList<>();

        for (int i = 0; i < array.size() / 2; i++)
        {
            left.add(array.get(i));
        }
        for (int i = array.size() / 2; i < array.size(); i++) 
        {
            right.add(array.get(i));
        }

        return mergeInt(mergeSortInt(left), mergeSortInt(right));
    }

    private static ArrayList<Integer> mergeInt(ArrayList<Integer> left, ArrayList<Integer> right)
    {
        if (left.size() == 0) return right;
        if (right.size() == 0) return left;

        ArrayList<Integer> result = new ArrayList<Integer>();

        int next;

        if (left.get(0) > right.get(0))
        {
            next = right.get(0);
            right.remove(0);
        }
        else 
        {
            next = left.get(0);
            left.remove(0);
        }

        result.add(next);
        result.addAll(mergeInt(left,right));

        return result;
    }

What exactly is a StackOverFlowError? And why does it only occur for a larger amount of numbers?

Thanks in advance :)

EDIT:

I don't really see how this is a duplicate since I'm also asking for help specifically with my code.

Method calls go on the stack. When you recurse to too deep a level, your _overflow_ your stack by trying to put too many things on it. It is similar (in an abstract way) to an infinite loop (or just a really long one) in code. — Jesan Fafon, May 13 '14 at 18:07
@JesanFafon - "When you *recur* too deeply ....". Yes, this often leaves you cursing repeatedly, but that's another word entirely. — Hot Licks, May 13 '14 at 18:15

score 0 · Answer 1 · answered May 13 '14 at 18:10

A StackOverflowError occurs when you have too many stored method environments on the stack. When one function calls another function, it has to store its variables and state in a stack frame. When the call to the other function returns, the original function's frame is popped and used to restore the function's state.

Since mergesort is a recursive algorithm, mergeInt will push another frame to the stack with every recursive call to itself. Mergesort requires a depth of log_2 n recursive calls, where n is the length of the input. Therefore, when you increase n, you increase the number of stack frames that have to be created and stored. If there are too many of those, you will get a StackOverflowError.

Mergesort: getting java.lang.StackOverflowError for 100000 numbers but not for 10000

1 Answers1