合并排序（merge_sort）代码无法正常排序，请求排查问题

嘿，我帮你找出了代码里导致排序失效的几个关键bug，咱们一个个拆解并修复：

1. Merge函数中左子数组拷贝错误 #

你在拷贝左子数组时写了：

for (i = 0;i < n_l;i++)
    Arr_l[i] = Arr[i];

这里的问题是，左子数组的起始位置是参数left，而不是数组的开头（索引0）。比如当处理left=5到mid=7的子数组时，应该从Arr[5]开始拷贝，而非Arr[0]。修正后代码：

for (i = 0;i < n_l;i++)
    Arr_l[i] = Arr[left + i];

2. Merge函数中循环变量未重置 #

拷贝完左右子数组后，i的值已经变成了n_l，j的值变成了n_r，这时候进入合并循环：

while (i < n_l && j < n_r) { ... }

循环条件直接不满足，合并逻辑根本不会执行！你需要在拷贝完数组后把i和j重置为0。修正后代码片段：

// 拷贝左子数组
for (i = 0;i < n_l;i++)
    Arr_l[i] = Arr[left + i];
// 拷贝右子数组
for (j = 0;j < n_r;j++)
    Arr_r[j] = Arr[mid + 1 + j];
// 重置循环变量，准备合并
i = 0;
j = 0;

3. Merge_sort_inc函数的递归边界错误 #

递归函数里有两个核心问题：

• mid计算错误：原代码mid = (int)((left + (right - 1)) / 2);会导致区间划分偏移，正确的mid计算应该是mid = left + (right - left) / 2;（这种写法还能避免整数溢出）。
• 右区间递归调用错误：你写的merge_sort_inc(Arr, mid + 1, right - 1);会让右子数组少处理一个元素，正确的右边界应该是right而非right-1。

修正后的merge_sort_inc函数：

void merge_sort_inc(int Arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        merge_sort_inc(Arr, left, mid);
        merge_sort_inc(Arr, mid + 1, right);
        merge(Arr, left, mid, right);
    }
}

4. Main函数中调用merge_sort_inc的参数错误 #

数组的索引范围是0到size-1，但你调用时传的是merge_sort_inc(Array, 0, size);，这里的size=10对应索引10，超出了数组的最大索引9，会导致越界访问。修正后调用代码：

merge_sort_inc(Array, 0, size - 1);

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void print_arr(int Arr[], int size) {
    int i;
    for (i = 0;i < size;i++)
        printf(" %d ", Arr[i]);
}

void merge(int Arr[], int left, int mid, int right) {
    int i = 0, j = 0, k = left;
    int n_l = (mid - left + 1);
    int n_r = (right - mid);
    int* Arr_l = (int*)calloc(n_l , sizeof(int));
    int* Arr_r = (int*)calloc(n_r , sizeof(int));
    if (Arr_l == NULL) return;
    if (Arr_r == NULL) return;

    // 拷贝左子数组，从left起始位置开始
    for (i = 0;i < n_l;i++)
        Arr_l[i] = Arr[left + i];
    // 拷贝右子数组
    for (j = 0;j < n_r;j++)
        Arr_r[j] = Arr[mid + 1 + j];
    
    // 重置循环变量，准备合并两个子数组
    i = 0;
    j = 0;

    while (i < n_l && j < n_r) {
        if (Arr_l[i] <= Arr_r[j]) {
            Arr[k] = Arr_l[i];
            i++;
            k++;
        } else {
            Arr[k] = Arr_r[j];
            j++;
            k++;
        }
    }
    // 拷贝左子数组剩余元素
    while (i < n_l) {
        Arr[k] = Arr_l[i];
        i++;
        k++;
    }
    // 拷贝右子数组剩余元素
    while (j < n_r) {
        Arr[k] = Arr_r[j];
        j++;
        k++;
    }
    free(Arr_l);
    free(Arr_r);
}

void merge_sort_inc(int Arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // 避免溢出的mid计算方式
        merge_sort_inc(Arr, left, mid);
        merge_sort_inc(Arr, mid + 1, right);
        merge(Arr, left, mid, right);
    }
}

int main() {
    int i;
    time_t t;
    srand((unsigned)time(&t));
    int Array[10];
    int size = sizeof(Array) / sizeof(int);
    for (i = 0;i < size;i++)
        Array[i] = rand() / 100;
    printf("The unsorted Array is : \n");
    print_arr(Array, size);
    printf("\n\nThe sorted Array is : \n");
    merge_sort_inc(Array, 0, size - 1); // 传入正确的右边界索引
    print_arr(Array, size);
    return 0;
}

内容的提问来源于stack exchange，提问作者Ali.Nemat