C++归并排序merge函数使用动态数组触发堆损坏问题

索引错位是核心bug #

你申请的临时数组temp是长度为last - first + 1的连续堆内存，它的合法索引范围是0到last - first，和原数组的全局下标没有任何对齐关系。
但你的代码里所有对temp的写入操作，都直接使用原数组的全局下标i（初始值为first）作为temp的索引：

• 举个实际调用场景：如果调用merge时first=2, mid=3, last=5，temp的实际长度是4，最大合法索引为3。但代码里i初始值为2，随着双指针推进，i会一直累加到5，此时访问temp[4]、temp[5]完全超出了申请的内存边界，直接破坏堆结构，触发Heap Corruption错误。
• 哪怕进入递归后部分合并区间起点为0、暂时没有越界，最后拷回原数组的环节同样存在逻辑错误：代码用arr[k] = temp[k]循环拷贝，k取原数组的全局下标，一旦合并区间起点大于0，就会越界访问temp内存。

为什么改成申请last + 1大小就能暂时不报错 #

这属于巧合性的内存越界掩盖：当你申请更大的内存块时，之前越界写入的位置刚好落在了你申请的堆内存的合法范围内，没有触发堆管理器的校验拦截。但本质的索引错位问题完全没有解决：

• 临时数组开头的空间始终存的是未初始化的垃圾值
• 错位的拷贝逻辑会把垃圾值覆盖回原数组的对应位置
• 这种“正常运行”只是没有触发crash，最终的排序结果是完全错误的。

正确的实现逻辑 #

要完全避免下标错位，必须把临时数组的索引和原数组的全局下标做严格的偏移映射，不要混用：

1. 临时数组从索引0开始存储合并后的元素，完全脱离原数组的下标体系
2. 所有写入temp的操作，都从0开始逐位累加
3. 从temp拷回原数组时，按照偏移关系计算位置：原数组的位置 = 起始位置first + temp的相对索引

修正后的代码如下：

void merge(int arr[], int first, int mid, int last) {
    int* temp = new int[last - first + 1];
    int temp_pos = 0;
    int left_start = first;
    int left_end = mid;
    int right_start = mid + 1;
    int right_end = last;

    // 双指针合并写入临时数组
    while (left_start <= left_end && right_start <= right_end) {
        if (arr[left_start] < arr[right_start]) {
            temp[temp_pos] = arr[left_start];
            left_start++;
        } else {
            temp[temp_pos] = arr[right_start];
            right_start++;
        }
        temp_pos++;
    }

    // 写入左区间剩余元素
    while (left_start <= left_end) {
        temp[temp_pos] = arr[left_start];
        left_start++;
        temp_pos++;
    }

    // 写入右区间剩余元素
    while (right_start <= right_end) {
        temp[temp_pos] = arr[right_start];
        right_start++;
        temp_pos++;
    }

    // 按偏移量拷回原数组
    for (int i = 0; i <= last - first; i++) {
        arr[first + i] = temp[i];
    }

    delete[] temp;
}

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