Merge Sort doesn't work for a table of integers with more than 521096 elements

Question

I am trying to sort a large table of integers using different types of sorting algorithms like quick sort, bubble sort and merge Sort, all of these algorithms works just fine. However, When trying to sort a table with more than than 521096 elements using Merge Sort, the program just exits without throwing any error(I'm guessing in C this is a runtime error)

Note that Merge Sort works perfectly with a table that contains less than 921096 elements. Note also that for example Quick Sort works fine with tables of any length(I've tried up to 1 Million elements).

Here is the code I'm using:

void fillTable(int *t,int n){
    srand(time(NULL));
    int signe=1;
    for(int *p=t;p<t+n;p++){
        *(p)=signe*rand()%n;
        signe*=-1;
    }
}
void mergeTables(int *tab,int l,int m,int r){
    int i,j,k;
    int n1=m-l+1;
    int n2=r-m; 


    int lTab[n1],rTab[n2];

    for(i=0;i<n1;i++){
        lTab[i]=tab[l+i];
    }
    for(i=0;i<n2;i++){
        rTab[i]=tab[m+1+i];
    }

    i=0;j=0;k=l;
    while(i<n1 && j<n2){
        if(lTab[i]<=rTab[j]){
            tab[k]=lTab[i];
            i++;
        }
        else{
            tab[k]=rTab[j];
            j++;
        }
        k++;
    }
    while(i<n1){
        tab[k]=lTab[i];
        i++;
        k++;
    }
    while(j<n2){
        tab[k]=rTab[j];
        j++;
        k++;
    }
}

void diviserTab(int *tab,int l,int r){
    if(r>l){
        int m=(r+l)/2;
        diviserTab(tab,l,m);
        diviserTab(tab,m+1,r);
        mergeTables(tab,l,m,r);
    }
}
void mergeSort(int* t,int n){
        diviserTab(t,0,n-1);
}
double getTime(void(*f)(int*,int),int* t,int n){
    clock_t start,end;
    start=clock();
    f(t,n);
    end=clock();
    return (double)(end-start)/CLOCKS_PER_SEC;
}

and here is my Main:

int main(){

int *tab;
int i;
int n=521096;
tab=(int*)malloc(n*sizeof(int));
fillTable(tab,n);
printf("First 10 elements before sorting");
for ( i = 0; i < 10; i++)
{
    printf("%5d\t",tab[i]);
}

printf("%f\n",getTime(mergeSort,tab,n));
printf("\nFirst 10 elements before sorting\n");
for ( i = 0; i < 10; i++)
{
    printf("%5d\t",tab[i]);
}


return 0;   

}

Now to the results: if n=521095 (number of elements in the array)

First 10 elements before sorting
18187   -12205  23363   -27523  30572   -31906   5475   -10341   5178   -27678
it took 0.179000 to sort the array

First 10 elements after sorting
-32767  -32767  -32767  -32767  -32767  -32767  -32767  -32766  -32766  -32766

if n=521096

First 10 elements before sorting
18243   -31088  32141   -10616   9312    -356   25619   -26113  23731   -21465

(and it just exits)

Answer 1

You are allocating some large arrays on the stack. From your mergeTables function:

int lTab[n1],rTab[n2];

With a large array to sort, n1 and n2, and therefore lTab and rTab, can become large (half the size of your initial array), and the stack is typically fairly small. If the arrays don't fit, all sorts of strange things can happen. When I tried your program with a large array (10 million integers), the program crashed.

Quicksort and bubble sort are usually performed in situ, so I assume you didn't need all this extra space for them.

I changed your two arrays to this:

int *lTab = malloc(n1 * sizeof(int));
int *rTab = malloc(n2 * sizeof(int));

And then at the end of the function:

free(lTab);
free(rTab);