合并排序不适用于具有超过521096个元素的整数表

Question

我正在尝试使用不同类型的排序算法（例如快速排序，冒泡排序和合并排序）对大型整数表进行排序，所有这些算法都可以正常工作。但是，当尝试使用“合并排序”对包含超过521096个元素的表进行排序时，程序仅退出而不会引发任何错误（我猜在C中这是运行时错误）

请注意，合并排序与包含少于921096元素的表完美配合。还要注意，例如，快速排序可用于任何长度的表（我已经尝试了多达100万个元素）。

这是我正在使用的代码：

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;
}

这是我的主语：

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;   

}

现在显示结果：如果n = 521095（数组中的元素数）

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

如果n = 521096

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

（它刚刚退出）

Answer 1

您正在堆栈上分配一些大数组。通过mergeTables功能：

int n1=m-l+1;
int n2=r-m;

int lTab[n1],rTab[n2];

[要排序的数组很大，n1和n2以及因此的lTab和rTab可以变大，并且堆栈通常很小。如果数组不合适，则可能发生各种奇怪的事情。当我尝试使用大型数组（1000万个整数）的程序时，程序崩溃了。

我将您的两个数组更改为此：

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

然后在函数末尾：

free(lTab);
free(rTab);