GESP 五级 · GESP 202409 C++ 五级 第 10 题

考虑以下 C++ 代码实现的归并排序算法：

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int L[n1], R[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

对长度为 $n$ 的数组 arr，调用函数 merge_sort(a, 0, n-1)。在排序过程中 merge 函数的递归调用次数大约是（ ）。

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

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

【考点】递归树节点数｜归并排序原理｜复杂度分析

【解题思维】

合并排序的递归结构天然形成一棵二叉树：每个非叶子节点代表一次 merge 调用，每个叶子节点对应一个基例（left ≥ right）。对于长度为 n 的数组，这棵递归树恰好有 n 个叶子（每个元素最终被单独归并一次），而内部节点数 = 叶子数 - 1 = n - 1。因此 merge 被调用的总次数是 n - 1，即 O(n)。

更本质的观察：merge 函数合并两个有序子数组，每次调用处理两个子数组中所有元素，但调用次数本身只取决于递归树的节点数量，与数组规模 n 呈线性关系。这是归并排序区别于其他分治算法的关键特征——合并操作次数正好等于元素个数，而合并过程本身（比较与移动）才是 O(n log n) 的来源。

【陷阱拆解】

选项 C 是典型的高度陷阱。许多考生看到递归分治就联想到树高 log₂n，误以为 merge 调用次数只与树高有关，完全忽略了树中节点总数才是调用次数的度量。命题人用"递归调用次数"这个表述，就是想卡住那些只记得"归并排序是 log n 层"却不懂递归树结构的考生。

选项 D 更阴险：O(n log n) 是归并排序的时间复杂度，考生很容易把"复杂度"与"调用次数"混为一谈。命题人把 merge 的调用次数作为独立问题，就是要检验你是否真正理解递归执行轨迹，而不是机械背诵结论。

选项 A 则针对另一种错误直觉——以为 merge 只在顶层调用一次。

【反命题思维】

如果题目改成问"merge_sort 函数的调用次数"，答案是 2n-1（每个节点都被调用一次，包括叶子）；如果问"总的比较次数"，最坏情况是 O(n log n)，平均情况则是 n log₂n - n = O(n log n)。

刷到类似题时，先问自己：题目问的是递归树的什么属性？节点数、高度、叶子数还是比较次数？归并排序的递归树节点总数 = 元素总数，这是铁律，一旦抓住这个本质，所有变式题都能一眼看穿。