GESP 五级 · GESP 202312 C++ 五级 第 2 题

下面 C++ 代码以递归方式实现合并排序，并假设 merge(int T[], int R[], int s, int m, int t) 函数将有序（同样排序规则）的 T[s..m] 和 T[m+1..t] 归并到 R[s..t] 中。横线处应填上代码是（ ）。

void mergeSort(int SList[], int TList[], int s, int t, int len)
{
    if (s == t){
        TList[s] = SList[s];
        return;
    }
    int *T2 = new int[len]; // 保存中间结果
    int m = (s + t) / 2;
    ________________________;
    merge(T2, SList, s, m, t);
    delete T2;
    return;
}

这题考的是递归分治中区间边界的精确划分。拿到题先别急着背模板，盯着代码里的 m 定义和 merge 函数的参数。merge 把 T[s..m] 和 T[m+1..t] 合起来，那递归拆分时，左半部分必须包含 m，右半部分从 m+1 开始，这样才能保证所有元素被处理且互不重复。

最容易掉进两个坑：一是死记硬背'左闭右开'的模板，看到 m 就下意识觉得它属于右边，结果选了把 m 漏掉的选项；二是没看清 merge 函数的参数顺序和范围，以为 merge 处理的是 [s, m-1] 和 [m, t]，其实题目明确写了 [s, m] 和 [m+1, t]。还有个隐蔽的坑是选项 A，它把 m 给了左边，但右边递归调用参数写成了 m, t，导致 m 被处理了两次，合并时会出现重复元素，这也是很多学生容易忽略的细节。

这道题考查递归与分治算法中的区间边界处理

考点与命题视角

题目属于 GESP 五级"算法"模块中递归与分治策略的综合应用。命题人卡住的是考生对递归调用区间边界的理解——很多人只背"左半部分 [s, m-1]，右半部分 [m, t]"的模板，却忽略了本题中 s 和 t 是包含的，导致选错。