GESP 五级 · GESP202609 C++ 五级 第 11 题

下面是归并排序中合并两个有序区间（升序排序）的部分代码。若希望排序保持稳定，横线处应填写 （　　）。

while (i <= mid && j <= right) {
if (__________________) {
temp.push_back(a[i++]);
} else {
temp.push_back(a[j++]);
}
}

归并排序合并阶段需同时维护有序性和稳定性。稳定性要求相等元素保持原序，而合并时左区间元素天然先出现，因此当 a[i] == a[j] 时必须优先取 a[i]。这意味着条件需满足：a[i] < a[j] 时取 a[i]，a[i] == a[j] 时也取 a[i]，即条件为 a[i] <= a[j]。

A 项 a[i] < a[j] 看似标准，却漏掉相等情形——当 a[i] == a[j] 时条件为假，会取 a[j]，破坏稳定性。B 项 a[i] > a[j] 更离谱，相等时仍取 a[j]，且会颠倒大小关系。C 项 a[i] >= a[j] 虽能保稳定，但会错误优先取右区间元素，违背合并逻辑。D 项 a[i] <= a[j] 是稳定归并的标准写法，相等时优先取左区间，完美兼顾有序与稳定。

1. 考纲定位

本题考查《GESP 考试大纲》五级算法模块中的归并排序与稳定性概念。命题人专门设置此题，是因为五级考生普遍能写出归并框架，却常在合并条件上栽跟头——要么误用 < 导致不稳定，要么混淆左右区间优先级。这道题就是卡住"知道归并但不懂稳定归并"的考生。

2. 解题思维

看到"稳定排序"四个字，立刻锁定稳定性定义：相等元素相对位置不变。归并时左右区间各自有序，合并过程就是逐个比较取最小。关键观察：左区间元素在原始数组中天然排在右区间前面。因此当 a[i] == a[j] 时，必须取 a[i] 才能保持原序。

数值推演：设左区间 [2, 5]，右区间 [2, 8]。比较 a[i]=2 与 a[j]=2，若条件为 <，则 2 < 2 为假，取 a[j]=2，输出序列变成 [2, 2, 5, 8]，两个 2 的相对位置被颠倒了——不稳定。若条件为 <=，则 2 <= 2 为真，取 a[i]=2，输出序列为 [2, 2, 5, 8]，两个 2 保持原序——稳定。

通法提炼：任何稳定归并的合并条件都必须是 a[i] <= a[j]。这是稳定排序的通用写法，可迁移到所有涉及稳定性的归并场景。