数据结构：递归式归并排序 (Recursive Merge Sort)-EW帮帮网

// 假设我们已经有了上一节写的 merge 辅助函数
// void merge(int arr[], int l, int m, int r) { ... }

// 递归式归并排序函数
// 它的任务是排序 arr 数组中从索引 l 到 r 的部分
void mergeSortRecursive(int arr[], int l, int r) {
    // 这是递归的终止条件，也是最重要的部分
    // 如果 l >= r，说明这个子数组最多只有一个元素，已经是有序的了
    if (l >= r) {
        return; // 直接返回，什么都不做
    }

    // 分解和合并的逻辑将在这里实现
}

第二阶段：实现“分解 (Divide)”和“解决 (Conquer)”

根据我们的推导，接下来要做的是找到中点，然后进行两个“信仰之跃”的递归调用。

void mergeSortRecursive(int arr[], int l, int r) {
    if (l >= r) {
        return;
    }

    // 1. 分解 (Divide): 找到中间点 m
    // 为了防止 l+r 溢出，推荐使用这种写法
    int m = l + (r - l) / 2; 

    // 2. 解决 (Conquer): 对左右两个子问题进行递归调用
    // 我们“相信”这两个函数调用结束后，左右两半就各自有序了
    mergeSortRecursive(arr, l, m);
    mergeSortRecursive(arr, m + 1, r);

    // 此时，arr[l...m] 和 arr[m+1...r] 都已经有序
    // 还差最后一步：合并
}

小提示：为什么用 m = l + (r - l) / 2 而不是 m = (l + r) / 2？因为如果 l 和 r 都是非常大的正整数，l + r 的结果可能会超出 int 类型的最大值，导致溢出。而 r - l 则不会有这个问题。这是一个更稳健的编程习惯。

第三阶段：实现“合并 (Combine)”

万事俱备，只欠东风。我们现在有两个已排序的子数组，只需要调用 merge 函数来完成最后的合并。

// 引入 merge 和 printArray 等辅助函数
#include <iostream>
// (这里应该包含你已经写好的 merge, swap, printArray 等函数)
// ...

void mergeSortRecursive(int arr[], int l, int r) {
    if (l >= r) {
        return;
    }

    int m = l + (r - l) / 2;

    mergeSortRecursive(arr, l, m);
    mergeSortRecursive(arr, m + 1, r);

    // 3. 合并 (Combine): 将两个有序的子数组合并
    std::cout << "Merging [" << l << "..." << m << "] and [" << m + 1 << "..." << r << "]\n";
    merge(arr, l, m, r);
}

// 主函数中需要一个启动调用的包装
void startMergeSort(int arr[], int n) {
    mergeSortRecursive(arr, 0, n - 1);
}

这个递归函数写起来非常简洁、优美，完美地体现了“分而治之”的思想。

举例模拟

理论过后，一个具体的例子是把知识“盘活”的最佳方式。

我们将用一个具体的数组，一步步画出递归式归并排序的完整调用树，让你清晰地看到“分解 (Divide)”和“合并 (Combine)”的全过程。

待排序数组：int arr[] = {8, 4, 3, 7, 1, 5, 6, 2};

数组大小：n = 8

初始调用：mergeSortRecursive(arr, 0, 7)

为了方便表示，我们把 mergeSortRecursive(l, r) 简写为 MS(l, r)。

分解过程 (Divide) - 递归向下

这是函数不断调用自身，将大问题分解为小问题的过程。在这一阶段，还没有执行任何 merge 操作。执行流会一直冲向最左边的“递归尽头”。

1. MS(0, 7)  // 初始调用, m = 3
      |
      +--> 2. MS(0, 3) // 左半部分, m = 1
            |
            +--> 3. MS(0, 1) // 左半部分的左半部分, m = 0
                  |
                  +--> 4. MS(0, 0) // 到达基本情况(l=r), 直接返回
                  |
                  +--> 5. MS(1, 1) // MS(0,1)的右半部分, 也是基本情况, 直接返回

当第5步 MS(1, 1) 执行完毕并返回后，第3步 MS(0, 1) 的两个递归子调用就都完成了。此时，第一个 merge 操作即将发生。

整个分解过程的完整调用路径如下所示，你可以想象成一个深度优先的遍历：

MS(0, 7) 调用 MS(0, 3)
MS(0, 3) 调用 MS(0, 1)
MS(0, 1) 调用 MS(0, 0) (返回)
MS(0, 1) 调用 MS(1, 1) (返回)
MS(0, 1) 的分解完成，开始合并
MS(0, 3) 调用 MS(2, 3)
MS(2, 3) 调用 MS(2, 2) (返回)
MS(2, 3) 调用 MS(3, 3) (返回)
MS(2, 3) 的分解完成，开始合并
MS(0, 3) 的分解完成，开始合并
MS(0, 7) 调用 MS(4, 7)
... (右半边树的分解过程与左半边类似) ...

合并过程 (Combine) - 递归向上返回

这是真正进行排序的阶段。当递归调用开始返回时，merge 函数会被执行，将已排序的子数组合并起来。

我们来一步步追踪数组 arr 的变化：

1️⃣MS(0, 1) 的合并

MS(0, 0) 返回，此时 arr[0] 是 {8} (已排序)
MS(1, 1) 返回，此时 arr[1] 是 {4} (已排序)
MS(0, 1) 现在执行 merge(arr, 0, 0, 1)。
合并 {8} 和 {4}，结果是 {4, 8}。
arr 状态: [**4, 8**, 3, 7, 1, 5, 6, 2]

2️⃣MS(2, 3) 的合并

MS(2, 2) 返回 ({3})，MS(3, 3) 返回 ({7})。
MS(2, 3) 执行 merge(arr, 2, 2, 3)。
合并 {3} 和 {7}，结果是 {3, 7}。
arr 状态: [4, 8, **3, 7**, 1, 5, 6, 2]

3️⃣MS(0, 3) 的合并

此时，MS(0, 1) 和 MS(2, 3) 都已完成。arr[0...1] 和 arr[2...3] 各自有序。
MS(0, 3) 现在执行 merge(arr, 0, 1, 3)。
合并 {4, 8} 和 {3, 7}，结果是 {3, 4, 7, 8}。
arr 状态: [**3, 4, 7, 8**, 1, 5, 6, 2]

4️⃣MS(4, 5) 的合并

(右半树开始合并) MS(4, 4) ({1}) 和 MS(5, 5) ({5}) 返回。
MS(4, 5) 执行 merge(arr, 4, 4, 5)。
合并 {1} 和 {5}，结果是 {1, 5}。
arr 状态: [3, 4, 7, 8, **1, 5**, 6, 2]

5️⃣MS(6, 7) 的合并

MS(6, 6) ({6}) 和 MS(7, 7) ({2}) 返回。
MS(6, 7) 执行 merge(arr, 6, 6, 7)。
合并 {6} 和 {2}，结果是 {2, 6}。
arr 状态: [3, 4, 7, 8, 1, 5, **2, 6**]

6️⃣MS(4, 7) 的合并

此时 arr[4...5] 和 arr[6...7] 各自有序。
MS(4, 7) 执行 merge(arr, 4, 5, 7)。
合并 {1, 5} 和 {2, 6}，结果是 {1, 2, 5, 6}。
arr 状态: [3, 4, 7, 8, **1, 2, 5, 6**]

7️⃣MS(0, 7) 的最终合并

这是最顶层的合并。此时 arr[0...3] 和 arr[4...7] 各自有序。
MS(0, 7) 执行 merge(arr, 0, 3, 7)。
合并 {3, 4, 7, 8} 和 {1, 2, 5, 6}。
- 1 < 3, 取 1
- 2 < 3, 取 2
- 3 < 5, 取 3
- 4 < 5, 取 4
- 5 < 7, 取 5
- 6 < 7, 取 6
- 7 < 8, 取 7
- 取 8
结果是 {1, 2, 3, 4, 5, 6, 7, 8}。
arr 最终状态: [**1, 2, 3, 4, 5, 6, 7, 8**]

递归调用树可视化

我们可以把整个过程画成一棵树。-> 符号表示该函数调用完成后的返回值（即排好序的子数组）。

                                      MS(0, 7) -> [1, 2, 3, 4, 5, 6, 7, 8]
                                     /                    \
                                    /                      \
                  MS(0, 3) -> [3, 4, 7, 8]                   MS(4, 7) -> [1, 2, 5, 6]
                 /            \                             /            \
                /              \                           /              \
      MS(0, 1) -> [4, 8]    MS(2, 3) -> [3, 7]        MS(4, 5) -> [1, 5]    MS(6, 7) -> [2, 6]
      /      \              /      \                  /      \              /      \
     /        \            /        \                /        \            /        \
MS(0,0)->[8] MS(1,1)->[4] MS(2,2)->[3] MS(3,3)->[7] MS(4,4)->[1] MS(5,5)->[5] MS(6,6)->[6] MS(7,7)->[2]

❓如何解读这棵树：

向下看（分解）：从根节点 MS(0, 7) 出发，沿着分支一路向下，直到最底层的叶子节点。这就是递归的“分”的过程，将大数组不断切分成小数组。
向上看（合并）：从最底层的叶子节点（它们天然有序）开始，每一层的父节点的值，都是由其左右两个子节点的值 merge 而来的。这个 merge 的过程就是排序的核心，它将两个有序的子序列合并成一个更长的有序序列，直到最终回到根节点，完成整个排序。

通过这个例子，你可以清晰地看到递归归并排序是如何通过优雅的“分而治之”策略，将一个复杂问题分解、解决、再合并的。

复杂度与特性分析

递归式归并排序的性能特性与迭代式几乎完全一样，因为它们做的“功”的总量是相同的，只是完成的顺序不同。

时间复杂度 (Time Complexity)

我们可以用一个递归关系式来描述它的时间复杂度。设 T(n) 是排序 n 个元素所需的时间。
- 分解问题：找到中点需要 O(1) 的时间。
- 解决子问题：需要 2 * T(n/2) 的时间来递归地排序两个子数组。
- 合并结果：需要 O(n) 的时间来合并两个子数组。
所以，T(n) = 2 * T (n / 2) + O(n)。
通过“主定理”或“递归树”等方法分析这个关系式，可以得出其解为 O(nlogn)。
这个分解和合并的过程与数据初始状态无关，因此最好、最坏和平均情况的时间复杂度都是：O(nlogn)

空间复杂度 (Space Complexity)

辅助数组空间：和迭代版本一样，merge 函数在执行时需要一个临时的辅助数组，其最大长度与原数组长度 n 成正比。这部分空间是 O(n)。
递归栈空间：每次函数调用都会在程序的调用栈上创建一个栈帧来保存局部变量和返回地址。递归的深度决定了栈空间的使用量。因为每次都将问题一分为二，所以递归的深度是 O(logn)。
总空间复杂度：O(n) (用于merge的数组) + O(logn) (用于递归栈) = O(n)。因为 O(n) 是主导项。

稳定性 (Stability)

递归算法的稳定性完全取决于合并操作 (merge 函数) 的稳定性。
只要我们在 merge 函数中，当遇到相等元素时，优先选择左边子数组的元素（正如我们之前实现的那样），那么整个排序算法就是稳定的。
因此，递归式归并排序是稳定的排序算法 (Stable Sort)。

递归 vs. 迭代

代码：递归版本的代码更短，更直观地反映了“分而治之”的思想，通常更容易编写。
性能：迭代版本没有函数调用和栈操作的开销，在理论上性能会略好一点，并且可以避免在数据量极大时可能出现的“栈溢出” (Stack Overflow) 风险。
核心逻辑：两者在计算量和最终结果上是等价的，只是一个“自顶向下”分解，一个“自底向上”构建。

数据结构：递归式归并排序 (Recursive Merge Sort)

从“分而治之”的视角出发

代码的逐步完善

第一阶段：定义函数框架和递归的“出口”