Recursive Insertion Sort Crashes for almost large n

Question

I wrote a Recursive Insertion Sort that works fine but the problem is the application stops working if I set n = 10000 or around 5000 and larger, no matter what the values of the array is. (Ex. vector array(10000,0) )

Here is the code :

void RecursiveInsertionSort(int i, vector<int> &arr)
{
    if (i <= 0)
        return;

    RecursiveInsertionSort(i - 1, arr);

    int key = arr[i];
    int j = i - 1;

    while (j >= 0 && arr[j] > key)
    {
        arr[j + 1] = arr[j];
        j--;
    }

    arr[j + 1] = key;

}

And I call it in the main like this :

vector<int> arr (10000,1);
RecursiveInsertionSort(arr.size() - 1, sorted);

I don't understand where the problem is.

score 3 · Answer 1 · edited May 23 '17 at 12:15

I think your problem is related to the maximum recursion level allowed in your environment. More details can be found here and here.

[edit]

If you do not control maximum recursion level (like in your case where the input can be quite large), it is best to avoid recursion and use an iterative algorithm (i.e. using while, for etc.). This issue is explained here and how to actually transform a recursive algorithm into a non-recursive one is very well covered in this article.

Recursive Insertion Sort Crashes for almost large n

1 Answers1