归并排序代码无法正常运行，输出与输入数组一致求排查

你的归并排序代码运行后输出与输入未排序数组完全一致，是因为存在三个关键错误，逐一排查并修正如下：

• mergeSort函数中mid值计算错误：原代码里mid = (low + mid) / 2中的mid是未初始化的局部变量，值为随机值，导致分治逻辑完全失效。正确写法是用当前区间的首尾索引计算中间位置：mid = (low + high) / 2。

• mergeSort调用时的high参数错误：main函数中调用mergeSort(array, 0, n)，但数组有效索引范围是0到n-1，传入n会让函数处理超出数组边界的元素，触发未定义行为。应改为mergeSort(array, 0, n-1)。

• main函数返回类型不符合C标准：C语言标准要求main函数返回类型必须为int，而非void，虽然这不会直接影响排序结果，但会引发编译警告，建议修正为int main()并在末尾添加return 0;。

修正后的完整代码 #

#include <stdio.h>

void merge(int array[], int mid, int low, int high) {
    int i, j, k, temp[100];
    
    i = low;
    k = low;
    j = mid + 1; 
    
    while (i <= mid && j <= high) {
        if (array[i] < array[j]) {
            temp[k] = array[i];
            i++;
            k++;
        } else {
            temp[k] = array[j];
            j++;
            k++;
        }
    }
    
    while (i <= mid) {
        temp[k] = array[i];
        i++;
        k++;
    }
    
    while (j <= high) {
        temp[k] = array[j];
        j++;
        k++;
    }
    
    for (int i = low; i <= high; i++) {
        array[i] = temp[i];
    }
}

void mergeSort(int array[], int low, int high) {
    int mid;
    if (low < high) {
        mid = (low + high) / 2; // 修正mid计算方式
        mergeSort(array, low, mid);
        mergeSort(array, mid + 1, high);
        merge(array, mid, low, high);
    }
}

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

int main() { // 修正main返回类型
    int array[100], n, p;
   
    printf("How many number you want to insert?\n");
    scanf("%d", &n);
   
    for (p = 0; p < n; p++) {
        scanf("%d", &array[p]);
    } 
    
    printArray(array, n);
    mergeSort(array, 0, n-1); // 修正high参数
    printArray(array, n);
    
    return 0; // 添加返回语句
}

运行示例 #

How many number you want to insert?
4
6
4
7
5
6  4  7  5 
4  5  6  7 

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