C语言归并排序仅支持2的幂次长度数组问题排查

你的代码核心问题是merge函数中数组与遍历变量的对应关系完全搞混，导致非2的幂次长度数组排序时出现越界访问，读取/写入垃圾值，具体错误点如下：

错误分析 #

1. 数组与索引变量不匹配：
   • arr2存储左半部分数组（长度left），对应遍历变量i；arr1存储右半部分数组（长度right），对应遍历变量j。但你在比较时写成了arr1[i] <= arr2[j]，这里i是左半部分的索引，超出arr1的长度范围，会越界读取内存中的随机值（表现为负数等异常值）。
2. 收尾循环赋值错误：
   • 剩余右半部分元素应该从arr1中取，你却用了arr2[j]；剩余左半部分元素应该从arr2中取，你却用了arr1[i]，导致复制错误的元素。

修复后的代码 #

修正后的merge函数 #

void merge(int t[], int l, int mid, int h)
{
    int left = mid - l + 1;
    int right = h - mid;
    int arr1[right]; // 存储右半部分：t[mid+1..h]
    int arr2[left];  // 存储左半部分：t[l..mid]

    for (int i = 0; i < right; i++)
    {
        arr1[i] = t[mid + i + 1];
    }
    for (int i = 0; i < left; i++)
    {
        arr2[i] = t[l + i];
    }

    int i = 0; // arr2（左半部分）的索引
    int j = 0; // arr1（右半部分）的索引
    int k = l;

    while (i < left && j < right)
    {
        // 修正：比较左半部分arr2[i]和右半部分arr1[j]
        if (arr2[i] <= arr1[j])
        {
            t[k] = arr2[i];
            i++;
        }
        else
        {
            t[k] = arr1[j];
            j++;
        }
        k++;
    }

    // 修正：复制剩余的左半部分元素（arr2）
    while (i < left)
    {
        t[k] = arr2[i];
        i++;
        k++;
    }

    // 修正：复制剩余的右半部分元素（arr1）
    while (j < right)
    {
        t[k] = arr1[j];
        j++;
        k++;
    }
}

保持不变的mergesort函数 #

void mergesort(int t[], int l, int h)
{
    if (l < h)
    {
        int mid = (l + h) / 2;
        mergesort(t, l, mid);
        mergesort(t, mid + 1, h);
        merge(t, l, mid, h);
    }
}

额外优化建议 #

• 避免使用变长数组（int arr1[right]这类），可以用动态内存分配malloc，避免栈溢出风险，尤其处理大数组时更安全。
• 计算mid时可以用l + (h - l)/2，避免l + h溢出（当数组长度极大时）。

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