归并排序代码遇内存问题：栈溢出或写入访问权限违规求排查

以下是你的代码中导致「栈溢出」和「写入访问权限违规」的核心问题，以及对应的修复方案：

1. 无限递归引发栈溢出 #

Mergesort 函数的递归边界处理错误：

Mergesort(a, l, mid);
Mergesort(a, mid, r);

当处理长度为1的子数组时（如 l=0, r=1），mid=0，右侧递归会重复传入 (0,1)，导致无限递归，最终触发栈溢出。

修复：将右侧递归的起始索引改为 mid+1，确保子数组不重叠且能收敛到单个元素：

Mergesort(a, l, mid);
Mergesort(a, mid + 1, r);

2. 缺少代码块括号导致逻辑错误 #

Merge 函数的 if-else 分支未用大括号包裹多行代码：

if (a[i] < a[j])
    b[k] = a[i];
    i++  // 缺少分号且不在if分支内
else 
    b[k] = a[j];
    j++;

这会导致 i++ 和 j++ 始终执行，与条件判断无关，进而引发数组越界访问（写入权限违规）。

修复：用大括号包裹分支内所有代码，并补充分号：

if (a[i] < a[j]) {
    b[k] = a[i];
    i++;
} else {
    b[k] = a[j];
    j++;
}

3. 按值传递vector导致无效修改与内存浪费 #

Merge 函数参数 vector<int> a 是按值传递，会创建原数组的副本。后续对 a 的修改仅作用于副本，无法影响原数组，同时大量复制大数组会加剧栈溢出风险。

修复：改为按引用传递：

void Merge(vector<int>& a, int l, int m, int r)

4. 错误的数组回写逻辑 #

Merge 函数最后将整个 b 数组复制回 a，但实际上只需要回写当前合并的子数组（l 到 r 的部分）：

for (int x = 0; x < a.size(); x++)
    a[x] = b[x];

这会覆盖原数组中未参与合并的元素，导致数据损坏，甚至访问未初始化内存。

修复：仅回写合并后的子数组：

for (int x = l; x <= r; x++) {
    a[x] = b[x - l];
}

5. 错误释放vector内存 #

delete &b; 是完全错误的操作：vector 是C++标准容器，会自动管理内存，离开作用域时会自动释放资源。手动调用 delete 操作栈上的vector对象会触发未定义行为，导致访问权限违规。

修复：直接删除这一行代码。

6. 合并区间边界不匹配 #

原代码中 Merge 函数的 j < r 逻辑与递归调用的边界不匹配，导致合并时遗漏最后一个元素。需要统一区间为闭区间（[l, r] 包含两端）。

修复：调整 Merge 函数中的循环条件：

while (i <= m && j <= r) { ... }
while (i <= m) { ... }
while (j <= r) { ... }

修复后的完整代码 #

#include <iostream>
#include <vector>
using namespace std;

void Merge(vector<int>& a, int l, int m, int r) {
    int i = l, j = m + 1, k = 0;
    vector<int> b(r - l + 1); // 仅分配需要的内存大小

    while (i <= m && j <= r) {
        if (a[i] < a[j]) {
            b[k] = a[i];
            i++;
        } else {
            b[k] = a[j];
            j++;
        }
        k++;
    }

    while (i <= m) {
        b[k] = a[i];
        k++;
        i++;
    }

    while (j <= r) {
        b[k] = a[j];
        k++;
        j++;
    }

    // 将合并后的结果回写原数组的对应区间
    for (int x = l; x <= r; x++) {
        a[x] = b[x - l];
    }
}

void Mergesort(vector<int>& a, int l, int r) {
    if (l >= r)
        return;
    int mid = l + (r - l) / 2;
    Mergesort(a, l, mid);
    Mergesort(a, mid + 1, r);
    Merge(a, l, mid, r);
}

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    Mergesort(a, 0, n - 1);

    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    return 0;
}

内容的提问来源于stack exchange，提问作者Ярослава Гурьева