我的MergeSort（归并排序）实现输出异常值，问题出在哪里？

• 核心触发原因：Merge函数中第一个循环是打印日志的逻辑，执行完后循环变量i已经等于n1，紧接着给left数组赋值的循环判断条件是i < n1，根本不会执行，left数组的所有元素都是未初始化的堆内存垃圾值，就是你看到的怪异数值来源。
• 索引逻辑错误：给left数组赋值时额外加了start == 0的判断，甚至非0情况还做了start + i -1的偏移，完全不符合归并排序的区间定义：left数组本应该存储原数组[start, mid)区间的元素，不需要额外的偏移判断，错误的索引会导致读取内存非法位置的值。
• 递归拆分错误：MergeSort函数递归拆分时第二个子数组传参是mid + 1，但你的Merge函数是按左闭右开区间[start, mid)、[mid, end)处理的，传mid +1会跳过mid位置的元素，导致排序结果缺值或者异常。

#include <iostream>
#include <limits>

void Merge(double A[], size_t start, size_t mid, size_t end)
{
    size_t n1 = mid - start;
    size_t n2 = end - mid;
    size_t i = 0;
    size_t j = 0;

    double* left = new double[n1 + 1];
    double* right = new double[n2 + 1];

    // 重置i后做赋值，不和打印逻辑共用迭代后的变量
    for (i = 0; i < n1; i++)
    {
        // 去掉错误偏移判断，直接取对应区间的值
        left[i] = A[start + i];
        // 打印逻辑可放在赋值后执行
        std::cout << left[i] << " ";
    }
    std::cout << std::endl;

    for (j = 0; j < n2; j++)
    {
        right[j] = A[mid + j];
    }

    left[n1] = std::numeric_limits<double>::infinity();
    right[n2] = std::numeric_limits<double>::infinity();

    i = 0;
    j = 0;
    for (size_t k = start; k < end; k++)
    {
        if (left[i] <= right[j])
        {
            A[k] = left[i];
            i++;
        }
        else
        {
            A[k] = right[j];
            j++;
        }
    }

    delete[] left;
    delete[] right;
}

void MergeSort(double A[], size_t start, size_t end)
{
    // 区间长度大于1才需要拆分排序
    if (end - start > 1)
    {
        size_t mid = (start + end) / 2;
        MergeSort(A, start, mid);
        // 第二个子数组从mid开始，不要加1避免跳过元素
        MergeSort(A, mid, end);
        Merge(A, start, mid, end);
    }
}

调用时如果待排序数组长度为len，直接传入MergeSort(arr, 0, len)即可正常执行。

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