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

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);
}