C++数据结构作业实现归并排序时5元素序列测试排序错误问题排查

你的实现存在3个核心逻辑错误，直接导致长度5以上的排序结果错乱：

• merge函数的处理逻辑完全不符合归并排序要求：归并操作的处理对象是数组内两个相邻、各自有序的子区间（左段为[left, mid]，右段为[mid+1, right]），但你当前的merge实现是直接用i=0（数组头）、j=size-1（数组尾）两个指针向中间遍历取值，根本没有拆分两个待归并的子序列。对测试用例的长度5输入{48,77,64,2,11}，你当前的merge逻辑直接输出的结果就是报错的{11,2,48,64,77}，序列中11>2完全违反升序规则。
• 递归边界与参数传递完全错位：你当前的mergesort内部每次都把begin硬编码为0，递归调用时传入的子数组范围完全混乱：比如长度为5的数组，计算得到mid=2后，第一个递归调用传的size是mid-1=1，第二个递归调用传的size是end=4，两个递归处理的区间高度重叠，根本没有实现“把原数组拆成左右两个独立子区间分别排序”的分治逻辑。
• 递归过程没有做结果回写：归并操作的结果是写入临时数组output的，但你每次递归读数据都是直接从原始的input里拿，没有把上一轮归并得到的有序结果同步回input，导致下一层递归读到的永远是未排序的原始乱序数据。

短长度测试通过是巧合：长度2/3/4的数组下，错位的递归逻辑刚好能输出和正确排序一致的结果，到长度5的场景下，参数错位和错误merge逻辑的影响被放大，就会触发测试失败。

按照归并排序的标准分治逻辑调整实现后，即可通过全部教授提供的测试用例，代码完全保留原有函数签名，不需要修改测试端内容：

// 归并input中[left, mid]和[mid+1, right]两个有序段到临时buffer
void merge(int *input, int left, int mid, int right, int *buffer, bool output_asc) {
    int i = left;    // 左段遍历指针起点
    int j = mid + 1;// 右段遍历指针起点
    int k = left;   // 输出位置起点
    while (i <= mid && j <= right) {
        if (output_asc) {
            // 升序规则：取两个指针中值更小的元素
            if (input[i] <= input[j]) {
                buffer[k++] = input[i++];
            } else {
                buffer[k++] = input[j++];
            }
        } else {
            // 降序规则：取两个指针中值更大的元素
            if (input[i] >= input[j]) {
                buffer[k++] = input[i++];
            } else {
                buffer[k++] = input[j++];
            }
        }
    }
    // 将两个段中剩余未遍历的元素直接写入buffer
    while (i <= mid) {
        buffer[k++] = input[i++];
    }
    while (j <= right) {
        buffer[k++] = input[j++];
    }
    // 将归并完成的有序结果从buffer写回原数组，供上层递归使用
    for (int p = left; p <= right; p++) {
        input[p] = buffer[p];
    }
}

// 递归实现：处理当前数组的[left, right]区间
void mergesort_recursive(int *input, int left, int right, int *buffer, bool output_asc) {
    if (left >= right) {
        return;
    }
    int mid = (left + right) / 2;
    // 递归排序左半段
    mergesort_recursive(input, left, mid, buffer, output_asc);
    // 递归排序右半段
    mergesort_recursive(input, mid + 1, right, buffer, output_asc);
    // 归并两个已排序的子段
    merge(input, left, mid, right, buffer, output_asc);
}

// 保留原有函数签名，兼容原有调用逻辑
void mergesort(int *input, int size, int *output, bool output_asc) {
    if (size <= 1) {
        return;
    }
    mergesort_recursive(input, 0, size - 1, output, output_asc);
}

// 保留原有对外接口，匹配测试代码的调用方式
int *mergesort(int *input, int size) {
    int *output = new int[size];
    // 复制原始数据作为排序的操作空间
    for (int i = 0; i < size; i++) {
        output[i] = input[i];
    }
    mergesort(output, size, output, true);
    return output;
}

• 归并排序的分治过程必须准确传递每个子问题的区间左右边界，不能每次硬编码从数组头部开始计算子问题范围。
• 归并完成后必须将临时buffer中的有序结果回写到操作数组，否则递归下层读到的永远是未排序的原始数据，无法累积排序效果。
• 归并操作的指针必须被限制在对应子段的范围内移动，不能直接用整段数组的首尾作为指针起点。

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