GESP 八级 · GESP 202512 C++ 八级 第 2 题

下列代码实现了归并排序（Merge Sort）的分治部分。为了正确地将数组 a 的 [left, right] 区间进行排序，横线处应该填入的是（ ）。

void merge_sort(int a[], int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    merge_sort(a, left, mid);
    _______; // 在此处填入选项
    merge(a, left, mid, right); // 合并操作
}

根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

【考点】递归｜分治算法｜数组区间划分

本题考查 GESP 八级算法模块“分治与递归”核心考点。命题人刻意将“递归调用区间”与“合并区间”混淆，卡住大量考生对分治边界条件的理解。

归并排序分治步骤：先排左半区 [left, mid]，再排右半区 [mid+1, right]，最后合并。代码已调用 merge_sort(a, left, mid) 完成左半排序，横线必须补全右半递归调用。观察 mid 是 left+right 除以 2 的中间点，右半区起始下标必然是 mid + 1。

错误选项均利用“区间端点混淆”设计陷阱：A、C、D 的 mid 或 mid+1 与已排序区间重叠，导致重复排序或遗漏元素。最阴险的是选项 A，mid 恰好是左半区终点，考生若误以为“递归区间包含 mid"，就会选它，但此时左半区已排完，再排 [mid, right] 就重复计算了 a[mid]。记住：分治的“分”意味着左右区间必须不重叠且覆盖原区间。

若将题目改为“排左半区”或“排右半区”，递归调用边界会相应偏移。刷到类似题，先问自己：“这段区间是否已被递归处理过？”避免重复或遗漏。