Why this Stackoverflow exception is occuring while implementing merge sort in java recursively?

Question

I'm basically trying implement merge sort in Java. For doing so, I've created a class called Array, which has an integer array a[]. The class also has a method called slice(int left, int right) that produces the slice of array and returns the object. Henceforth , there is a sort() method that recursively calls itself and breaks down the array and returns an Array object at the end.

import java.util.*;
class Array
{
    int a[];

    public Array()
    {
        a = null;
    }

    public Array(int x)
    {
        a = new int[x];
    }  

    public void input()
    {
        Scanner sc = new Scanner(System.in);
        for(int i = 0; i < a.length; i++)
        {
            System.out.print("Enter a No. = ");
            a[i] = sc.nextInt(); 
        }
    }

    public void display()
    {
        for(int i = 0; i < a.length; i++)
            System.out.print(a[i] + "\t");
        System.out.println();
    }

    public Array slice(int left, int right)
    {
        Array ob = new Array(left + right + 1);
        for(int i = left; i <= right; i++)
            ob.a[i] = this.a[i];
        return ob;
    }

    public static Array merge(Array A, Array B)
    {
        Array C = new Array(A.a.length + B.a.length);
        int i, j, k;
        i = j = k = 0;

        while(i < A.a.length && j < B.a.length)
        {
            if(A.a[i] < B.a[j])
                C.a[k++] = A.a[i++];
            else if(A.a[i] > B.a[j])
                C.a[k++] = B.a[j++];
            else
            {
                C.a[k++] = A.a[i++]; j++;
            }
        }

        while(i < A.a.length)
            C.a[k++] = A.a[i++];

        while(j < B.a.length)
            C.a[k++] = B.a[j++];

        return C;
    }

    public Array sort()
    {
        if(this.a.length == 1)
            return this;
        else
        {
            return merge(this.slice(0, (this.a.length - 1) / 2).sort(), this.slice(1 + (this.a.length - 1) / 2, this.a.length - 1).sort());
        }
    }

    public static void main()
    {        
        Array x;
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the No. of Elements = ");
        Array ob = new Array(sc.nextInt());
        ob.input();
        System.out.println("\n ORIGINAL ARRAY");
        ob.display();
        System.out.println("\n SORTED ARRAY");
        x = ob.sort();
        x.display();
    }
}

Suppose if I have an object A, which has an integer array a[], then on calling A.sort() must return an object in which all the array elements will be sorted in ascending order.

Error(s) I Got: java.lang.StackOverflowError: null

Answer 1

The stack is a region of memory of finite size. It's often not that big. When you call a recursive function, each recursive call is placed on the stack. When the recursion finishes, the calls on the stack are popped off and executed.

The problem is if your array is big, and the recursion goes to deep (many calls), you might run out of space on the stack to put the next recursive call. This is a stack overflow.

I made exactly the same mistake at uni once. :)

To fix your program you can:

• increase the stack size (this is a hack, there is still a limit to how many recursive calls you can make, it's just higher now)
• decrease the memory use of each call (still kind of a hack, probably not very effective either, unless you're storing large data in a local variable)
• implement your merge sort iteratively so that you only deal with small pieces of data at a time, instead of putting it all on the stack first, then dealing with it at the end.

Every recursive algorithm can be implemented with iteration (a loop).

Answer 2

Firstly, your slice should be implemented like this. I suspect this is the main problem. The way you did it, the slices aren't getting smaller, so the recursion never bottoms out.

public Array slice(int left, int right)
{
    int length = right - left; // this is the proper length
    Array ob = new Array(length);
    for(int i = 0; i < length; i++)
        ob.a[i] = this.a[i + left];
    return ob;
}

Secondly, merge should be like this.

public static Array merge(Array A, Array B)
{
    Array C = new Array(A.a.length + B.a.length);
    int i = 0, j = 0, k = 0;

    while(i < A.a.length && j < B.a.length)
    {
        if(A.a[i] < B.a[j])
            C.a[k++] = A.a[i++];
        else if(A.a[i] > B.a[j])
            C.a[k++] = B.a[j++];
        else
        {
            C.a[k++] = A.a[i++];
            C.a[k++] = B.a[j++]; // this preserves duplicates
        }
    }

    while(i < A.a.length)
        C.a[k++] = A.a[i++];

    while(j < B.a.length)
        C.a[k++] = B.a[j++];

    return C;
}

Then sort becomes

public Array sort()
{
    if(a.length < 2)
        return this;

    int half = a.length / 2;
    Array left = slice(0, half).sort();
    Array right = slice(half, a.length).sort();
    return merge(left, right);
}