递归实现C语言归并排序出错：数组未正确排序且元素丢失

你的代码核心问题出在merge函数中，合并时写入原数组的起始下标k被错误初始化为0，而正确的初始值应该是si（当前要合并的子数组在原数组中的起始索引）。

错误分析 #

当递归处理原数组的某个子区间（比如从si到ei）时，合并操作需要将临时数组A和B中的元素写回原数组的**si到ei区间**，而不是从数组的起始位置（下标0）开始覆盖。如果k初始化为0，每次合并都会从数组开头写入数据，直接覆盖掉前面已经排好序的元素，这就导致了元素丢失和最终排序结果错误。

比如递归处理右半部分子数组（如si=3, ei=5）时，合并后的元素会被写到arr[0]、arr[1]、arr[2]，而不是目标位置arr[3]、arr[4]、arr[5]，直接破坏了左半部分已经排好的结果。

修正后的代码 #

只需要修改merge函数中k的初始值：

void merge(int arr[], int si, int mid, int ei) {
    int n1 = mid - si + 1, n2 = ei - mid;
    int A[n1], B[n2];
    
    for (int i = 0; i < n1; i++) {
        A[i] = arr[si + i];
    }

    for (int j = 0; j < n2; j++) {
        B[j] = arr[mid + j + 1];
    }
    
    // 修正k的初始值为si
    int i = 0, j = 0, k = si;
    while (i < n1 && j < n2) {
        if (A[i] <= B[j]) {
            arr[k++] = A[i++];
        } else {
            arr[k++] = B[j++];
        }
    }
    while (i < n1) {
        arr[k++] = A[i++];
    }
    while (j < n2) {
        arr[k++] = B[j++];
    }
}

修改后运行代码，数组会被正确排序为1,2,4,5,6,7。

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