GESP 八级 · GESP 202509 C++ 八级 第 13 题

下面 merge_sort 函数试图实现归并排序算法，横线处应该填入的是（ ）。

#include <vector>
using namespace std;
void merge_sort(vector<int> & arr, int left, int right) {
    if (right - left <= 1)
        return;
    int mid = (left + right) / 2;
    merge_sort(__________); // 在此处填入选项
    merge_sort(__________); // 在此处填入选项

    vector<int> temp(right - left);
    int i = left, j = mid, k = 0;
    while (i < mid && j < right)
        if (arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    while (i < mid)
        temp[k++] = arr[i++];
    while (j < right)
        temp[k++] = arr[j++];
    for (i = left, k = 0; i < right; ++i, ++k)
        arr[i] = temp[k];
}

A. 1 arr, left, mid 2 arr, mid, right

B. 1 arr, left, mid + 1 2 arr, mid + 1, right

C. 1 arr, left, mid 2 arr, mid + 1, right

D. 1 arr, left, mid + 1 2 arr, mid + 1, right + 1

STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。

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

【考点】递归（归并排序）｜区间边界

1. 🎯 考纲定位

GESP 八级 算法与程序设计模块，归并排序是递归思想的典型应用。命题人用这道题卡住的是考生对「递归区间」的理解——多数人会凭直觉把 mid 当成分割线，却忘了归并排序的合并阶段需要左右两个区间「首尾相接」，这题就是专门测试你是否看懂了合并循环里的 i < mid 与 j < right 这两个条件。