GESP 五级 · GESP 202512 C++ 五级 第 9 题

下面代码实现了归并排序。下述关于归并排序的说法中，不正确的是（ ）。

void merge(vector<int>& arr, vector<int>& temp, int l, int mid, int r) {
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    for (int p = l; p <= r; p++) arr[p] = temp[p];
}

void mergeSort(vector<int>& arr, vector<int>& temp, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(arr, temp, l, mid);
    mergeSort(arr, temp, mid + 1, r);
    merge(arr, temp, l, mid, r);
}

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】分治算法｜时间复杂度推导｜递归式 T(n)=2T(n/2)+O(n)

1. 本题考查 GESP 五级《算法》模块中“排序算法”与“时间复杂度”的交叉考点。命题人故意把归并排序与冒泡排序的复杂度混淆，卡住那些只背结论、没推导过 T(n)=2T(n/2)+O(n) 递归式的考生。

2. 归并排序是典型的分治算法：递归拆分到单元素，再两两合并。时间复杂度推导为 T(n)=2T(n/2)+O(n) → O(n log n)，无论数据有序与否都稳定。空间复杂度来自临时数组 temp，为 O(n)。

3. A 正确，归并排序的平均与最坏复杂度均为 O(n log n)；B 正确，需要 O(n) 额外空间存储 temp；D 正确，O(n log n) 适合大规模数据。C 错得离谱：O(n^2) 是冒泡排序的复杂度，命题人用绝对化表述“最坏情况”诱导考生把归并和冒泡混为一谈。

4. 若把 mergeSort 改成冒泡排序，C 就会正确、A 变错；若问空间复杂度，B 是标准答案。刷到这类题先问：命题人想考我什么？他是在测试递归复杂度推导，还是混淆不同排序算法？