归并排序（Merge sort）代码无法输出排序数组且报运行时错误

核心问题点 #

• 递归拆分逻辑错误导致栈溢出：你当前使用mid = ceil((low+high)/2)的计算方式完全错误，low+high是整数运算，除法默认向下取整，ceil对整数结果无意义，会导致子区间拆分进入死递归，耗尽程序栈空间直接崩溃。
• 临时数组下标越界：Merge函数中你将临时数组Temp的起始下标直接设置为当前子数组的起始下标low，但Temp的长度仅为当前子数组的长度high-low+1，下标范围是0~(high-low)，当low>0时直接写Temp[c]会触发越界访问，产生内存错误。
• 数组拷贝逻辑错误：最后将临时数组内容拷贝回原数组时，你遍历了0~high的所有位置，会错误覆盖子区间外的元素，且和临时数组的下标不对应。

修正后代码 #

#include<stdio.h>

void Merge(int arr[], int low, int mid, int high);

void printArray(int *arr, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void MergeSort(int arr[], int low, int high)
{
    int mid;
    if(low < high)
    {
        // 正确计算中点，避免溢出，无需ceil函数
        mid = low + (high - low) / 2;
        // 拆分左右子区间
        MergeSort(arr, low, mid);
        MergeSort(arr, mid + 1, high);
        // 合并两个有序子区间
        Merge(arr, low, mid, high);
    }
}

void Merge(int arr[], int low, int mid, int high)
{
    int i = low, j = mid + 1, c = 0;
    int Temp[high - low + 1];

    while(i <= mid && j <= high)
    {
        if(arr[i] < arr[j])
        {
            Temp[c++] = arr[i++];
        }
        else
        {
            Temp[c++] = arr[j++];
        }
    }    

    while(i <= mid)
    {
        Temp[c++] = arr[i++];          
    }
    while(j <= high)
    {
        Temp[c++] = arr[j++];
    }
    
    // 正确将临时数组内容拷贝回原数组对应区间
    for(int k = low; k <= high; k++)
    {
        arr[k] = Temp[k - low];
    }    
}

int main(void)
{
    int arr[] = {3,5,2,13,12,3,2,13,45};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("unsorted array: \n");
    printArray(arr, n);
    MergeSort(arr, 0, n-1);
    printf("sorted array: \n");
    printArray(arr, n);
    return 0;
}

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