归并排序实现异常：仅能完成数组前4个元素的排序

我参照《算法导论（第三版）》实现归并排序，但运行效果不符合预期——该实现仅能对数组的前4个元素进行排序。以下是我的实现代码：

#include <stdio.h>

void sortArr(int *nums, int arrSize) {
    // nums[start...end]
    // nums[start...mid]  n1
    // nums[mid+1...end]  n2
    int start, mid, end;
    start = 0;
    end = arrSize-1;
    mid = (end + start) / 2;
    int n1, n2;
    n1 = mid - start + 1;
    n2 = end - mid;
    int l[n1], r[n2];
    for (int i = 0; i < n1; i++) {
        l[i] = nums[start + i];
    }

    for (int i = 0; i < n2; i++) {
        r[i] = nums[mid + 1 + i];
    }

    int i, j;
    i = 0;
    j = 0;
    for (int k = start; k < arrSize; k++) {
        if (l[i] <= r[j]) {
            nums[k] = l[i];
            i++;
        } else {
            nums[k] = r[j];
            j++;
        }
    }
}

问题分析 #

• 缺少递归分治逻辑：归并排序的核心是递归拆分数组，把每个子数组排好序后再合并。当前代码只做了一次拆分和合并，完全没处理左右子数组的排序——如果数组长度大于4，左右子数组本身是无序的，合并后自然只能得到局部有序的结果。
• 合并阶段无边界判断：合并时没检查i是否超过左子数组长度、j是否超过右子数组长度。当其中一个子数组的元素先被合并完，继续访问l[i]或r[j]会触发数组越界，导致不可控的错误。

修正后的代码 #

#include <stdio.h>

// 合并两个有序子数组：nums[start...mid] 和 nums[mid+1...end]
void merge(int *nums, int start, int mid, int end) {
    int n1 = mid - start + 1;
    int n2 = end - mid;
    int l[n1], r[n2];
    
    // 复制左子数组元素
    for (int i = 0; i < n1; i++) {
        l[i] = nums[start + i];
    }
    // 复制右子数组元素
    for (int i = 0; i < n2; i++) {
        r[i] = nums[mid + 1 + i];
    }
    
    int i = 0, j = 0;
    int k = start;
    // 合并两个有序数组
    while (i < n1 && j < n2) {
        if (l[i] <= r[j]) {
            nums[k] = l[i];
            i++;
        } else {
            nums[k] = r[j];
            j++;
        }
        k++;
    }
    
    // 处理左子数组剩余的元素
    while (i < n1) {
        nums[k] = l[i];
        i++;
        k++;
    }
    // 处理右子数组剩余的元素
    while (j < n2) {
        nums[k] = r[j];
        j++;
        k++;
    }
}

// 递归实现归并排序：对nums[start...end]范围排序
void mergeSort(int *nums, int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        // 递归排序左半部分
        mergeSort(nums, start, mid);
        // 递归排序右半部分
        mergeSort(nums, mid + 1, end);
        // 合并两个有序子数组
        merge(nums, start, mid, end);
    }
}

// 对外接口：启动归并排序
void sortArr(int *nums, int arrSize) {
    mergeSort(nums, 0, arrSize - 1);
}

// 测试用例
int main() {
    int nums[] = {9, 3, 7, 5, 6, 4, 8, 2};
    int size = sizeof(nums) / sizeof(nums[0]);
    sortArr(nums, size);
    for (int i = 0; i < size; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

修正说明 #

1. 拆分出merge函数专门负责合并逻辑，补充了剩余元素的处理，避免数组越界问题。
2. 新增mergeSort递归函数，实现分治逻辑：当子数组长度大于1时，不断拆分并递归排序，最后合并有序子数组。
3. 保留sortArr作为对外调用的接口，内部调用递归函数完成完整排序。

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