用于计时排序算法的程序数组规模超20k时崩溃，求助排查

你的程序在数组规模超过20k时崩溃，核心原因是内存分配错误，同时还有几个小问题需要修正：

1. 致命错误：calloc参数误用 #

calloc的正确用法是calloc(元素个数, 每个元素的字节大小)，但你写成了：

int *arr1 = (int *)calloc(arr_lenght, arr_lenght * sizeof(int));

这会分配arr_lenght * arr_lenght * sizeof(int)字节的内存，当数组大小为20k时，计算下来是20000200004=1600000000字节（约1.5GB），远远超出程序能申请的内存上限，直接导致内存分配失败或后续访问越界崩溃。

修正后的内存分配代码：

int *arr1 = (int *)calloc(arr_lenght, sizeof(int));
int *arr2 = (int *)calloc(arr_lenght, sizeof(int));

或者用malloc更直观：

int *arr1 = (int *)malloc(arr_lenght * sizeof(int));

2. 次要问题修正 #

• 拼写错误：变量名arr_lenght应为arr_length（虽然不影响运行，但符合代码规范）
• clock()返回值类型错误：clock()返回的是clock_t类型，不是int，当程序运行时间较长时，int可能会溢出，应改为：

  clock_t ticks_start = clock();
  clock_t ticks_finish = clock();
  

• 输出格式冗余：可以合并printf语句，简化代码结构

修复后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "sorting.h"

#define ARG_COUNT 1

int main(int argc, char *argv[]) {
    
    if (argc != ARG_COUNT + 1) {
        printf("Too few or too many arguments passed.\n");
        exit(1);
    }

    int arr_length = atoi(argv[1]);
    if (arr_length < 10000) {
        printf("Array length should be at least 10000.\n");
        exit(2);
    }

    srand(time(0));

    // 修正内存分配参数
    int *arr1 = (int *)calloc(arr_length, sizeof(int));
    for (int i = 0; i < arr_length; i++) {
        arr1[i] = rand() % 20;
    }

    int *arr2 = (int *)calloc(arr_length, sizeof(int));
    for (int i = 0; i < arr_length; i++) {
        arr2[i] = rand() % 20;
    }

    // INSERTION SORT TIMER
    clock_t ticks_start = clock();
    insertion_sort(arr1, arr_length);
    clock_t ticks_finish = clock();

    double insertion_time = (double)(ticks_finish - ticks_start) / CLOCKS_PER_SEC;
    printf("insertion sort time: %f\n", insertion_time);
    
    // MERGE SORT TIMER
    ticks_start = clock();
    merge_sort(arr2, 0, arr_length - 1);
    ticks_finish = clock();

    double merge_time = (double)(ticks_finish - ticks_start) / CLOCKS_PER_SEC;
    printf("merge sort time: %f\n", merge_time);

    // 释放内存
    free(arr1);
    free(arr2);

    return 0;
}

额外说明 #

• 如果你用malloc分配内存，记得初始化（calloc会自动将内存清零，而malloc不会），不过这里你后续会给数组元素赋值，所以影响不大。
• 插入排序在数组规模较大时（比如10k以上）性能会急剧下降，这是算法本身O(n²)的时间复杂度决定的，属于正常现象，和程序崩溃无关。

内容的提问来源于stack exchange，提问作者yourdad