Suggestion for chkstk.asm stackoverflow exception in C++ with Visual Studio 2010

Question

I am working with an implementation of merge sort. I am doing C++ Visual Studio 2010. But when I took a array of 300000 integers for timing, it is showing an unhandled stackoverflow exception and taking me to a readonly file named "chkstk.asm". I reduced the size to 200000 and it worked. Again the same code worked with C-free 4 editor (mingw 2.95) without any problem while the size was 400000. Do you have any suggestion to get the code working in Visual Studio?

May be the recursion in the mergesort is causing the problem.

Answer 1

My guess is that you've got so much recursion that you're just running out of stack space. You can increase your stack size with the linker's /F command line option. But, if you keep hitting stack size limits you probably want to refactor the recursion out of your algorithm.

Answer 2

I'm not exactly sure, but this may be a particular problem of your implementation of yor merge sort (that causes stack overflow). There are plenty of good implementations (use google), the following works on VS2008 with array size = 2000000.

(You could try it in VS2010)

#include <cstdlib>
#include <memory.h>

// Mix two sorted tables in one and split the result into these two tables.
void Mix(int* tab1, int *tab2, int count1, int count2)
{
   int i,i1,i2;
   i = i1 = i2 = 0;
   int * temp = (int *)malloc(sizeof(int)*(count1+count2));

   while((i1<count1) && (i2<count2))
   {
      while((i1<count1) && (*(tab1+i1)<=*(tab2+i2)))
      {
         *(temp+i++) = *(tab1+i1);
         i1++;
      }
      if (i1<count1)
      {
         while((i2<count2) && (*(tab2+i2)<=*(tab1+i1)))
         {
            *(temp+i++) = *(tab2+i2);
            i2++;
         }
      }
   }

   memcpy(temp+i,tab1+i1,(count1-i1)*sizeof(int));
   memcpy(tab1,temp,count1*sizeof(int));

   memcpy(temp+i,tab2+i2,(count2-i2)*sizeof(int));
   memcpy(tab2,temp+count1,count2*sizeof(int));
   free(temp);
}

void MergeSort(int *tab,int count) {
   if (count == 1) return;

   MergeSort(tab, count/2);
   MergeSort(tab + count/2, (count + 1) /2);
   Mix(tab, tab + count / 2, count / 2, (count + 1) / 2);
}

void main() {
   const size_t size = 2000000;
   int* array = (int*)malloc(sizeof(int) * size);
   for (int i = 0; i < size; ++i) {
      array[i] = rand() % 5000;
   }

   MergeSort(array, size);
}

Answer 3

Problem solved. Thanks to Kotti for supplying the code. I got the problem while comparing with that code. The problem was not about too much recursion. Actually I was working with a normal C++ array which was being stored on stack. Thus the problem ran out of stack space. I just changed it to a dynamically allocated array with the new/delete statements and it worked.