一维动态数组正元素MergeSort排序失效问题排查

核心问题及修复 #

1. 排序函数索引参数错误

调用归并排序时传入的last参数不符合数组索引规则：

MergeSort(arrp, 0, n); 

数组arrp的元素个数是n，索引范围为0到n-1，传入n会导致Merge函数访问超出数组边界的内存，触发未定义行为，直接打乱排序逻辑。
修复：将参数改为数组最后一个元素的索引n-1

MergeSort(arrp, 0, n-1); 

2. 打印对象错误

排序完成后打印的是原数组arr，而非排序后的目标数组arrp：

printf("\nSorted array: ");
for (i = 0; i < n; i++)
    printf("%d ", arr[i]);

这会导致你看到的始终是未排序的原数据，误以为排序未执行。
修复：改为打印排序后的arrp

printf("\nSorted array: ");
for (i = 0; i < n; i++)
    printf("%d ", arrp[i]);

3. Merge函数临时数组内存分配不足

Merge中临时数组mas的内存计算少了1个元素：

mas = (int *)malloc((last - first) * sizeof(int));

当first到last包含last-first+1个元素时，只分配last-first大小的内存会导致越界写入，破坏内存结构，让排序中途失效。
修复：调整分配大小为last - first + 1，同时添加内存释放避免泄漏

mas = (int *)malloc((last - first + 1) * sizeof(int));
// ... 原有复制逻辑 ...
free(mas); // 在Merge函数末尾添加

4. 未定义的check()函数

main函数中调用了未实现的check()函数，直接导致编译失败。可以用已有的input()函数替代，因为input()已经包含输入校验逻辑：

printf("Input num of elements in mass: ");
n = input(); // 替换n = check();

修正后的完整代码 #

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

int input() {
    int var;
    while ((scanf_s("%d", &var) == 0) || getchar() != '\n') {
        printf("wrong input! try again\n");
        rewind(stdin);
    }
    return var;
}

void Merge(int *A, int first, int last) {
    int middle, start, final, j;
    int *mas;
    middle = (first + last) / 2; 
    start = first; 
    final = middle + 1; 
    // 修正内存分配大小
    mas = (int *)malloc((last - first + 1) * sizeof(int));
    for (j = first; j <= last; j++) 
        if ((start <= middle) && ((final > last) || (A[start] < A[final]))) {
            *(mas + j - first) = A[start];
            start++;
        } else {
            *(mas + j - first) = A[final];
            final++;
        }
    
    for (j = first; j <= last; j++)
        A[j] = *(mas + j - first);
    // 释放临时内存
    free(mas);
}

void MergeSort(int *A, int first, int last) {
    if (first < last) {
        MergeSort(A, first, (first + last) / 2); 
        MergeSort(A, (first + last) / 2 + 1, last); 
        Merge(A, first, last);
    }
}

int main() {
    int i, n, j;
    int *arr;
    int *arrp;
    printf("Input num of elements in mass: ");
    // 替换未定义的check()为input()
    n = input();
    arr = (int *)malloc(n * sizeof(int));
    for (i = 0; i < n; i++) {
        printf("Element %d = ", i + 1); 
        arr[i] = input();
    }
    for (i = 0; i < n; i++) {
        printf("%d  ", arr[i]);
    }
    printf("\n");

    for (i = 0; i < n; i++) {
        if (arr[i] < 0) {
            for (j = i; j < n - 1; j++) {
                arr[j] = arr[j + 1];
            }
            i--;
            n--;
        }
    }
    arrp = (int *)malloc(n * sizeof(int));
    for (i = 0; i < n; i++) {
        arrp[i] = arr[i];
        printf("%d  ", arrp[i]);
    }
    printf("\n");
    // 修正排序函数的last参数为n-1
    MergeSort(arrp, 0, n-1); 
    printf("\nSorted array: ");
    // 修正打印对象为排序后的arrp
    for (i = 0; i < n; i++)
        printf("%d ", arrp[i]);
    free(arrp);
    free(arr);
}

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