recursive insertion sort method giving StackOverflowError

Question

I am trying to analyze the Insertion Sort recursive method in Java for different arrays of size n. It sorts fine for small array sizes, but when I try to test it for let's say an array size of 32000, it gives me a StackOverflowError.

Is there a way to resolve this? I am using eclipse IDE.

The recursive algorithm I am using is below:

    ...

    @Override
    public int[] recursiveSort(int[] list)
    {
        // Start the clock
        this.startTime = System.nanoTime();

        count = 0;

        int n = list.length;

        insertionSortRecursive(list, n);

        // Stop the clock
        this.stopTime = System.nanoTime();

        return list;
    }

     // Recursive function to sort an array using insertion sort
    static void insertionSortRecursive(int arr[], int n)
    {
        count++;

        // Base case
        if (n <= 1)
            return;

        // Sort first n-1 elements
        insertionSortRecursive( arr, n - 1 );

        // Insert last element at its correct position in sorted array.
        int last = arr[n - 1];
        int j = n - 2;

        // Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position.
        while (j >= 0 && arr[j] > last)
        {
            count++;
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = last;
    }

score 0 · Answer 1 · answered Jan 27 '18 at 23:45

There is nothing wrong with your insertion sort implementation. It's just memory issue while keeping track of stack call. You can just quickly go through this link for more details. Even though, we can update some of JVM parameter to increase stack memory (refer here), but eventually this issue will happen for some other size (e.g. 64k, 128k, etc). So I would recommend you to change to normal iterative implementation instead of recursion.

recursive insertion sort method giving StackOverflowError

1 Answers1