Stackoverflow error while implementing insertion sort using recursion

Question

public static void insertionSortRecursion(String a[], int first, int last) {
        if (first < last) {
            //sort all but last
            insertionSortRecursion(a, first, last - 1);
            insertInOrder(a[last], a, first, last -1);
        }
    }

    private static void insertInOrder(String element, String[] a, int first, int last) {
//        System.out.println(last - 1);
//        System.out.println(element);
//        System.out.println(a[last]);
        if (element.compareTo(a[last]) >= 0) {
            a[last + 1] = element;
        } else if(first < last) {
            a[last + 1] = a[last];
            insertInOrder(element, a, first, last - 1);
        } else {
            a[last + 1] = a[last];
            a[last] = element;
        }
    }

Hey Guys, I am trying to implement insertion sort using recursion it's working fine on small number of words but I am getting stackoverflow after implementing it because the size of file I am sorting have a lot of words around 10,000. Please suggest what should I do to remove the error.

These are the methods I am using for insertion sort using recursion and I am calling them in my constructor.

Answer 1

Assuming your algorithm is correct, leave this function as it is. Don't try to fix it. In general to get rid of stack overflow (while keeping recursion) there are two solutions :

• Use tail call optimization
• Increase the stack size

But let sit back and assume this code is going to be anything else than a programming exercise. Any other person who have to read will think :

1. Why does he use insertion sort ?
2. Why does he re-implement insertion-sort?
3. Did it have to be recursion?? my lord!!
4. Why did he waste his time to find a tail-call insertion algorithm? Or
5. Did he just increased the stack size for the only sake of running his method?
6. Good. Now we have 1000,000 items to sort and the program keep crashing.

Conclusion, they will erase your code at once and use Collections.sort(). As I said, if you are doing a programming exercise then good, your recursive insertion sort work till some point. move on.

Answer 2

Java is not able to handle a recursion depth that deep (10000) by default. Consider the below oversimplified example still throws a StackOverflowError.

static void test(int i)
{
   if (i == 0) return;
   test(i-1);
}

public static void main(String[] args)
{
   test(10000);
}

You must specify command-line parameters to achieve this (-Xss and possibly -Xmx to allocate more memory).

I ran your algorithm successfully for an array of size 100000 using -Xmx1000m -Xss10000000 (though it took a while).

I assume there a reason you're using recursion and not a simple double for loop.