Merge Sort 归并排序原理和复杂度

新数组 = [] left指针 → 1, right指针 → 2 → 1 < 2 → 取 1，新数组 [1]，left指针后移 left指针 → 4, right指针 → 2 → 4 > 2 → 取 2，新数组 [1,2]，right指针后移 left指针 → 4, right指针 → 3 → 4 > 3 → 取 3，新数组 [1,2,3]，right指针后移 left指针 → 4, right指针 → 5 → 4 < 5 → 取 4，新数组 [1,2,3,4]，left指针后移 left指针 → 6, right指针 → 5 → 6 > 5 → 取 5，新数组 [1,2,3,4,5]，right指针后移 right已空 → 将 left 剩余 [6] 直接追加 → 最终 [1,2,3,4,5,6]

---

## 递归过程全览（图文步骤示意）

假设我们要排序的数组为 `[38, 27, 43, 3, 9, 82, 10]`。

### 拆分阶段

```text
原始数组:          [38, 27, 43, 3, 9, 82, 10]
拆分 1:      [38, 27, 43, 3]       [9, 82, 10]
拆分 2:   [38, 27]    [43, 3]    [9, 82]   [10]
拆分 3: [38] [27]   [43] [3]   [9] [82]  [10]

当拆成单个元素时，每个子数组已经是有序的（长度为1自然有序）。

合并阶段（自底向上归并）

[38] [27]   → 合并成 [27, 38]
[43] [3]    → 合并成 [3, 43]
[27, 38] 与 [3, 43] → 合并成 [3, 27, 38, 43]

[9] [82]   → 合并成 [9, 82]
[9, 82] 与 [10] → 合并成 [9, 10, 82]

[3, 27, 38, 43] 与 [9, 10, 82] → 最终合并成 [3, 9, 10, 27, 38, 43, 82]

每次合并都利用“合并两个有序数组”的算法，保证合并后的数组依然有序。

时间复杂度分析

归并排序无论数组初始状态如何，都会执行完整的拆分与合并过程，因此其最好、最差和平均时间复杂度都是 O(n log n)。

推导过程

• 拆分：每次将数组对半分，直到长度为1，拆分次数与二叉树高度相同，深度为 log₂n。
• 合并：每一层递归中，所有子数组的合并操作会遍历整个数组中的每个元素，即每一层的总操作量为 O(n)。
• 因此总复杂度 = 层数 × 每层工作量 = O(n log n)。

递归树示例（n=8）

层数（拆分后）         每层合并总元素量
第0层: n=8            合并为大小为8的数组 → O(8)
第1层: 两个 n/2=4     两个合并各O(4) → 合计 O(8)
第2层: 四个 n/4=2     四个合并各O(2) → 合计 O(8)
第3层: 八个 n/8=1     长度为1无需合并

总层级为 log₂8 = 3 层（不含大小为1的层），每层 O(n)，因此总共 O(3×8) = O(24)，即 O(n log n)。

空间复杂度

归并排序需要额外的数组来存放合并过程中的有序结果，因此空间复杂度为 O(n)。

• 在合并两个子数组时，需要临时创建一个新数组来存储合并后的数据。这个临时数组长度等于两个子数组长度之和。
• 递归过程中，同一时刻可能存在的临时数组总大小不会超过原数组长度（取决于实现方式，使用原地归并可以降低，但通常都不是原地的）。
• 另外递归调用栈的深度为 O(log n)，因此总空间 = O(n) + O(log n) = O(n)。

这使归并排序成为非原地排序（out-of-place），对于内存敏感的大数据场景需要特别注意。

稳定性

归并排序是稳定排序。

稳定性指相等元素的相对顺序在排序后保持不变。在合并两个有序数组时，如果两个指针指向的元素相等，我们优先取左边子数组的元素，这样就能保证相等元素的原始先后顺序。伪代码如下：

如果 left[i] <= right[j]，取 left[i] (优先保留左边元素)
否则取 right[j]

正是这个 <= 保证了对左数组的优先处理，从而实现了稳定性。

优缺点与应用场景

优点

• 时间复杂度稳定在 O(n log n)，不受输入数据影响。
• 稳定排序，适用于需要保持原始顺序的场景。
• 特别适合链表排序，因为链表的合并操作不需要额外空间，空间复杂度可优化至 O(1)。
• 适用于外部排序（数据太大无法全部装入内存），可分割成多个小文件排序后再多路归并。

缺点

• 需要 O(n) 额外内存，对数组排序时内存开销大。
• 相比快速排序，常数因子更大，实际运行速度可能稍慢。

伪代码实现

递归版本核心逻辑

函数 mergeSort(arr):
    如果 arr 长度 <= 1，直接返回 arr
    
    找到中点 mid = length // 2
    left = mergeSort(arr[0...mid-1])
    right = mergeSort(arr[mid...end])
    
    返回 merge(left, right)

函数 merge(left, right):
    创建空数组 result
    i = 0, j = 0
    当 i < len(left) 且 j < len(right):
        如果 left[i] <= right[j]:
            将 left[i] 加入 result
            i++
        否则:
            将 right[j] 加入 result
            j++
    
    // 将剩余元素加入
    将 left[i...] 全部加入 result
    将 right[j...] 全部加入 result
    
    返回 result