归并排序（Merge Sort）详解

分治策略与稳定排序 C++ 实现

算法概念与分治思想

归并排序（Merge Sort）是一种高效、基于分治（Divide and Conquer）策略的排序算法。

核心思想包含三个步骤：

分割 (Divide): 将当前待排序的序列递归地分割成两个规模大致相等的子序列，直到子序列的长度为 1（天然有序）。
解决 (Conquer): 递归地排序这两个子序列。
合并 (Merge): 将两个已经排序好的子序列合并成一个大的有序序列。

主要特点：

稳定排序：相等元素的原始相对顺序在排序后保持不变。
时间复杂度：无论最好、最坏还是平均情况，都是 O(n log n)。
空间复杂度：需要额外的辅助空间，通常是 O(n)。

递归分割 (Divide)

分割阶段的目标是将大数组不断对半切分，直到每个子数组只包含一个元素。这个过程是递归的。

假设我们有一个数组 `arr`，要对其 `[left, right]` 区间进行排序：

如果 `left >= right`，说明区间只有一个或零个元素，无需分割，直接返回。
计算中间索引 `mid = left + (right - left) / 2;` （这种写法可以防止 `left + right` 溢出）。
递归调用 `mergeSort(arr, left, mid);` 对左半部分进行分割和排序。
递归调用 `mergeSort(arr, mid + 1, right);` 对右半部分进行分割和排序。

点击下方按钮查看分割动画

合并有序子数组 (Merge)

合并是归并排序的关键步骤。当递归返回时，我们需要将两个已排序的子数组（例如 `arr[left...mid]` 和 `arr[mid+1...right]`）合并成一个单一的、有序的数组。

合并通常使用双指针法：

创建一个临时数组 `temp`，大小足以容纳两个子数组。
设置两个指针 `i` 和 `j`，分别指向两个子数组的起始位置。
比较 `arr[i]` 和 `arr[j]`：将较小的元素复制到 `temp` 中，并将对应指针向后移动。
重复上一步，直到其中一个子数组的所有元素都被复制。
将另一个子数组中剩余的所有元素直接复制到 `temp` 的末尾。
最后，将临时数组 `temp` 中的所有元素复制回原数组 `arr` 的对应位置 `[left...right]`。

左子数组:

右子数组:

↓ 合并中 ↓

临时数组:

↓ 完成后复制回 ↓

结果数组:

递归调用示意图

归并排序的递归调用过程可以用一棵树来形象地表示。根节点是原始数组，每个非叶子节点代表一次 `mergeSort` 调用，它的两个子节点代表对其左右子数组的递归调用。叶子节点是长度为 1 的数组（天然有序）。合并操作发生在从叶子节点向上返回的过程中。

点击下方按钮生成递归树

观察这棵树可以帮助理解：

递归深度： 树的高度大约是 log₂(n)，这就是时间复杂度中 log n 的来源。
合并顺序： 合并操作总是发生在子问题解决之后，自底向上进行。

时间 & 空间复杂度分析

时间复杂度: O(n log n)

归并排序的时间复杂度可以通过递归关系式推导：T(n) = 2T(n/2) + O(n)

`2T(n/2)`：代表递归排序两个规模为 n/2 的子问题所需的时间。
`O(n)`：代表合并两个已排序子数组所需的时间（线性扫描）。
递归树有 `log n` 层，每层合并操作的总时间复杂度是 `O(n)`。
因此，总时间复杂度为 O(n log n)。这在最好、最坏和平均情况下都成立。

O(n log n) 归并排序

O(n²) 冒泡排序
(比较)

空间复杂度: O(n)

归并排序的主要空间开销来自于合并过程中需要使用的临时数组。

在每次合并 `arr[left...mid]` 和 `arr[mid+1...right]` 时，需要一个大小为 `right - left + 1` 的临时空间。在递归实现中，虽然每次合并都可能分配空间，但同一层递归的合并操作可以复用空间（如果实现得当），或者最坏情况下，整个数组大小的临时空间就足够了。
递归调用本身也需要栈空间，深度为 `O(log n)`。
综合来看，主要的额外空间是 O(n) 的临时数组，因此总空间复杂度为 O(n)。

稳定性

归并排序是稳定的排序算法。在合并过程中，如果遇到两个相等的元素（一个来自左子数组，一个来自右子数组），我们总是优先将左子数组中的元素放入临时数组。这样就保证了原始顺序中排在前面的相等元素，在排序后仍然排在前面。

小测验：巩固知识

编程练习：动手实践

练习 1：实现递归版归并排序

请根据前面学到的知识，在下面的 C++ 代码框架中，补充完成递归版本的归并排序函数 `mergeSort` 和 `merge`。

// 包含必要的头文件
#include 
#include 
#include  // std::copy

// 合并函数：将 arr[left...mid] 和 arr[mid+1...right] 合并
void merge(std::vector& arr, int left, int mid, int right) {
    // TODO: 实现合并逻辑
    // 1. 计算两个子数组的大小
    // 2. 创建临时数组（或使用一个足够大的全局/成员临时数组）
    // 3. 使用双指针合并两个子数组到临时数组
    // 4. 处理剩余元素
    // 5. 将临时数组的内容复制回原数组的对应区间
}

// 归并排序主函数（递归）
void mergeSort(std::vector& arr, int left, int right) {
    // TODO: 实现递归分割和调用合并
    // 1. 递归终止条件
    // 2. 计算中间点 mid
    // 3. 递归排序左半部分
    // 4. 递归排序右半部分
    // 5. 合并已排序的左右两部分
}

// 测试代码 (示例)
int main() {
    std::vector data = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(data, 0, data.size() - 1);
    std::cout << "Sorted array: ";
    for (int x : data) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    return 0;
}

练习 2：实现非递归（自底向上）归并排序

尝试实现一个非递归版本的归并排序。这种方法通常称为自底向上（Bottom-Up）归并排序。它首先合并长度为 1 的子数组得到长度为 2 的有序子数组，然后合并长度为 2 的子数组得到长度为 4 的有序子数组，依此类推，直到整个数组有序。

#include 
#include 
#include  // std::min, std::copy

// 复用上面的 merge 函数
// void merge(std::vector& arr, int left, int mid, int right) { ... }

void mergeSortBottomUp(std::vector& arr) {
    int n = arr.size();
    if (n <= 1) return;

    // merge 函数需要一个临时数组，可以在这里创建一次，避免重复分配
    std::vector temp(n);

    // sub_len 是当前要合并的子数组长度 (1, 2, 4, 8, ...)
    for (int sub_len = 1; sub_len < n; sub_len *= 2) {
        // 遍历所有需要合并的相邻子数组对
        // i 是每对子数组的起始索引
        for (int i = 0; i < n - sub_len; i += 2 * sub_len) {
            // TODO: 计算左、中、右边界，并调用 merge
            // int left = i;
            // int mid = ?
            // int right = ?
            // 注意处理边界情况，特别是最后一个子数组可能不够长
            // merge(arr, left, mid, right, temp); // 假设 merge 函数接受 temp 参数
        }
    }
}

// 测试代码 (示例)
int main() {
    std::vector data = {38, 27, 43, 3, 9, 82, 10};
    mergeSortBottomUp(data);
    std::cout << "Sorted array (Bottom-Up): ";
    for (int x : data) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    return 0;
}

注意事项与知识延伸

实现注意事项

区间表示：统一区间的表示方式，常用左闭右闭 `[left, right]` 或左闭右开 `[left, right)`。本教程示例使用 `[left, right]`。
中间点计算：使用 `mid = left + (right - left) / 2` 来防止整数溢出，尤其当 `left` 和 `right` 都很大时。
递归基准情况：确保递归有正确的终止条件，通常是 `left >= right`。
合并边界：在 `merge` 函数中，仔细处理指针 `i` 和 `j` 的边界，确保不会越界访问数组。正确处理一个子数组先耗尽的情况。
空间优化：
- 可以尝试优化临时数组的使用，例如，对于小规模子数组改用插入排序（混合排序），或者在递归的奇偶层之间交替使用原数组和辅助数组，减少数据拷贝。
- 非递归版本天然地更容易控制和复用临时空间。
栈溢出风险：对于超大规模数组，极深的递归可能导致栈溢出。此时非递归实现是更好的选择。

知识延伸

外部排序 (External Sorting)：当数据量极大，无法完全加载到内存时，归并排序是外部排序的基础。可以将数据分块读入内存排序，然后使用多路归并（K-way Merge）合并这些已排序的块。
多路归并 (K-way Merge)：合并 K 个已排序的序列。常使用最小堆（Min-Heap）来高效地找到 K 个序列当前最小的元素，时间复杂度为 O(N log K)，其中 N 是总元素数量。
与快速排序的对比：
- 稳定性：归并排序是稳定的，快速排序通常不稳定。
- 时间复杂度：归并排序最坏情况仍为 O(n log n)，快速排序最坏为 O(n²)，但平均性能通常优于归并（常数因子更小）。
- 空间复杂度：归并排序需要 O(n) 额外空间，快速排序（原地版本）需要 O(log n) 递归栈空间。
- 适用场景：需要稳定性或保证最坏情况性能时选归并；对空间敏感或追求平均速度时常选快速排序。
应用场景：
- 需要稳定排序的场合（如按多个关键字排序）。
- 外部排序。
- 并行排序算法的基础。
- 用于解决其他问题，如计算逆序对数量。

感谢学习！希望本次讲解对你理解归并排序有所帮助。