Part 3.3：归并排序：稳定高效的分治典范

引言：稳定性的代价与价值

在上一篇文章中，我们学习了快速排序——平均性能最优但不稳定的排序算法。今天，我们将学习它的”孪生兄弟”——归并排序 (Merge Sort)，一个保证 O(n log n) 时间复杂度且稳定的排序算法。

归并排序由约翰·冯·诺依曼在 1945 年发明，是分治思想的又一经典体现。虽然它需要额外的 O(n) 空间，但其稳定性和可预测的性能使其在许多场景中不可替代。

为什么归并排序重要？

稳定性保证：当需要保持相等元素的相对顺序时（如多关键字排序），归并排序是首选。
外部排序：处理无法一次性加载到内存的大数据时，归并排序是最佳选择。
并行化：归并排序天然适合并行计算，在多核处理器上性能优异。

本文将带你深入理解归并排序的原理、实现和应用。

1. 核心原理：分解与合并

归并排序采用分治策略，其思想可以概括为两个步骤：

**分解 (Divide)**：将数组递归地分成两半，直到每个子数组只有一个元素（单个元素天然有序）。
**合并 (Merge)**：将两个已排序的子数组合并成一个有序数组。

关键图示：归并排序的递归树

图示：

初始数组: [38, 27, 43, 3, 9, 82, 10]

分解过程:
        [38, 27, 43, 3, 9, 82, 10]
       /                          \
  [38, 27, 43, 3]              [9, 82, 10]
   /           \                /         \
[38, 27]     [43, 3]         [9, 82]     [10]
 /    \       /    \          /    \
[38]  [27]  [43]  [3]       [9]  [82]

合并过程:
[27, 38]     [3, 43]         [9, 82]     [10]
   \           /                \         /
  [3, 27, 38, 43]              [9, 10, 82]
       \                          /
        [3, 9, 10, 27, 38, 43, 82]

2. 核心操作：合并 (Merge)

归并排序的核心是合并两个已排序数组的过程。

算法思路

假设我们要合并两个已排序的子数组 left 和 right：

创建一个临时数组 temp。
使用两个指针 i 和 j 分别指向 left 和 right 的开头。
比较 left[i] 和 right[j]，将较小的元素放入 temp，并移动对应的指针。
重复步骤 3，直到某一个数组的元素全部放入 temp。
将另一个数组的剩余元素全部放入 temp。
将 temp 复制回原数组。

动画式案例

合并 [27, 38] 和 [3, 43]：

i=0, j=0：比较 27 和 3，3 更小，放入 temp → [3]，j++
i=0, j=1：比较 27 和 43，27 更小，放入 temp → [3, 27]，i++
i=1, j=1：比较 38 和 43，38 更小，放入 temp → [3, 27, 38]，i++
left 已用完，将 right 剩余元素放入 → [3, 27, 38, 43]

伪代码

function mergeSort(arr, left, right):
  if left < right:
    mid = (left + right) // 2
    mergeSort(arr, left, mid)
    mergeSort(arr, mid + 1, right)
    merge(arr, left, mid, right)

function merge(arr, left, mid, right):
  // 创建临时数组
  L = arr[left...mid]
  R = arr[mid+1...right]
  
  i = 0, j = 0, k = left
  
  // 合并
  while i < len(L) and j < len(R):
    if L[i] <= R[j]:
      arr[k] = L[i]
      i++
    else:
      arr[k] = R[j]
      j++
    k++
  
  // 复制剩余元素
  while i < len(L):
    arr[k] = L[i]
    i++, k++
  
  while j < len(R):
    arr[k] = R[j]
    j++, k++

Python 实现

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

# 使用
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr) # 输出: [3, 9, 10, 27, 38, 43, 82]

3. 复杂度分析

时间复杂度

所有情况：O(n log n)。无论数据如何分布，归并排序的时间复杂度都是稳定的。
- 分解：log n 层（二分）
- 合并：每层需要 O(n) 时间
- 总时间：O(n log n)

空间复杂度

O(n)：需要额外的临时数组来存储合并结果。

稳定性

稳定。在合并时，如果 left[i] == right[j]，我们总是先取 left[i]，从而保持了相等元素的相对顺序。

4. 归并排序的应用

4.1 外部排序

当数据量巨大，无法一次性加载到内存时（如排序 100GB 的文件），可以使用归并排序的思想：

将大文件分成多个小文件，分别排序。
使用多路归并，将这些小文件合并成一个大的有序文件。

4.2 计算逆序对

问题：给定一个数组，计算其中有多少对 (i, j) 满足 i < j 但 arr[i] > arr[j]。

解法：在归并排序的合并过程中，当从右子数组取元素时，说明左子数组中剩余的所有元素都与该元素构成逆序对。

时间复杂度：O(n log n)，远优于暴力的 O(n²)。

4.3 链表排序

归并排序非常适合链表排序，因为链表的合并操作不需要额外空间，只需修改指针。

5. 归并排序 vs 快速排序

特性	归并排序	快速排序
时间复杂度（最坏）	`O(n log n)`	`O(n²)`
空间复杂度	`O(n)`	`O(log n)`
稳定性	稳定	不稳定
原地排序	否	是
实际性能	稳定但需额外空间	通常更快
适用场景	需要稳定性、外部排序、链表排序	一般场景、内存排序