C++实现Merge Sort时调用merge函数出现segmentation fault段错误

你的归并排序段错误完全由merge函数的多处逻辑错误、索引错误导致，具体问题及修复方案如下：

错误列表 #

• 索引初始化错误：左子数组起始索引i错误初始化为1，实际应该取传入的左边界l；临时数组temp的起始索引k错误初始化为1，应该初始化为0。
• 临时数组空间分配错误：你分配的new int[r]空间大小不足，当前合并的子数组范围是[l, r]，总共有r - l + 1个元素，需要分配对应长度的空间，否则会发生数组越界访问，直接触发段错误。
• 代码块嵌套错误：剩余元素复制的两个while循环、临时数组回写原数组的for循环，被错误嵌套在最外层的while (i <= m && j <= r)循环内部，导致每轮外层循环都会重复执行剩余元素复制，k值会快速超出临时数组边界触发越界。
• 分支逻辑错误：else分支内重复写了和外层一致的if (A[i] <= A[j])判断，导致右子数组的元素永远不会被写入临时数组，逻辑完全失效。
• 索引自增错误：右子数组复制的while循环内错误写了i++，应该是j++，这会导致i无限制自增，访问A[i]越界直接触发段错误，同时j永远不会自增导致死循环。
• 数组回写逻辑错误：回写临时数组到原数组时，错误从原数组的0号索引开始覆盖，且长度计算错误，应该只覆盖当前合并的[l, r]区间。
• 内存泄漏：临时数组temp分配后没有执行delete[]释放空间。

修正后的完整merge函数 #

void merge(int A[], int l, int m, int r) {
    int i = l; // 左子数组起始索引取左边界
    int j = m + 1; // 右子数组起始索引正确
    int k = 0; // 临时数组从0号索引开始存

    int len = r - l + 1;
    int *temp = new int[len]; // 分配刚好的空间

    // 两个子数组都有剩余元素时对比插入
    while (i <= m && j <= r) {
        if (A[i] <= A[j]) {
            temp[k] = A[i];
            i++;
        } else {
            temp[k] = A[j];
            j++;
        }
        k++;
    }

    // 复制左子数组剩余元素，放在外层循环外
    while(i <= m){
        temp[k] = A[i];
        i++;
        k++;
    }

    // 复制右子数组剩余元素，修正自增变量为j
    while(j <= r){
        temp[k] = A[j];
        j++;
        k++;
    }

    // 回写temp到原数组的[l, r]区间，不要覆盖其他位置
    for(int z = 0; z < len; z++){
        A[l + z] = temp[z];
    }

    // 释放临时数组空间，避免内存泄漏
    delete[] temp;
}

替换原merge函数后程序即可正常运行。

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