1. 概述
在本教程中，我们将讨论如何使用迭代算法实现归并排序。首先我们会简单回顾归并排序的基本原理及其递归实现。
随后，我们将详细介绍归并排序的迭代实现方式，并通过一个简单示例帮助理解其工作流程。
最后，我们还会对比递归与迭代实现的差异，并讨论在不同场景下的选择建议。
2. 归并排序原理
归并排序是一种高效的排序算法，其时间复杂度为 **O(n × log n)**，其中 n 是数组的元素个数。
通常我们见到的归并排序是递归实现的，基于“分治法”策略：
- 分（Divide）：将数组从中间一分为二
- 治（Conquer）：递归地对左右两部分排序，再合并两个有序数组为一个有序数组
递归排序的过程是自顶向下的，而迭代版本则是自底向上的实现方式。
3. 迭代实现方式
3.1 基本思路
迭代实现的核心思路是：从单个元素开始，逐步合并相邻的有序段，直到整个数组有序。
具体步骤如下：
- 初始状态下，将每个元素视为一个有序段
- 合并相邻的两个元素，形成长度为 2 的有序段
- 继续合并相邻的两个有序段，形成更长的有序段
- 不断重复，直到整个数组有序
整个过程是“自底向上”的，与递归方式相反。
3.2 合并函数
我们先实现一个合并函数，用于合并两个相邻的有序子数组：
algorithm Merge(A, L1, R1, L2, R2):
// INPUT
// A = the array to be sorted
// L1 = 起始位置 of 第一个子数组
// R1 = 结束位置 of 第一个子数组
// L2 = 起始位置 of 第二个子数组
// R2 = 结束位置 of 第二个子数组
// OUTPUT
// 返回合并后的有序数组
temp <- []
index <- 0
while L1 <= R1 and L2 <= R2:
if A[L1] <= A[L2]:
temp[index] <- A[L1]
L1 <- L1 + 1
else:
temp[index] <- A[L2]
L2 <- L2 + 1
index <- index + 1
while L1 <= R1:
temp[index] <- A[L1]
index <- index + 1
L1 <- L1 + 1
while L2 <= R2:
temp[index] <- A[L2]
index <- index + 1
L2 <- L2 + 1
return temp
该函数使用三个 while 循环完成合并：
✅ 第一个循环：依次比较两个子数组的元素，将较小者放入临时数组
✅ 第二个循环：处理第一个子数组剩余的元素
✅ 第三个循环：处理第二个子数组剩余的元素
⚠️ 该函数的时间复杂度为 **O(len1 + len2)**，其中 len1 和 len2 分别是两个子数组的长度。
3.3 迭代归并排序实现
现在我们基于上面的 merge 函数实现完整的迭代归并排序：
algorithm IterativeMergeSort(A, n):
// INPUT
// A = the array
// n = the size of the array
// OUTPUT
// sorted array
len <- 1
while len < n:
i <- 0
while i < n:
L1 <- i
R1 <- i + len - 1
L2 <- i + len
R2 <- i + 2 * len - 1
if L2 >= n:
break
if R2 >= n:
R2 <- n - 1
temp <- Merge(A, L1, R1, L2, R2)
for j <- 0 to R2 - L1 + 1:
A[i + j] <- temp[j]
i <- i + 2 * len
len <- 2 * len
return A
关键逻辑如下：
len表示当前每段的长度，初始为 1- 外层循环：每次将
len翻倍，直到len >= n - 内层循环：按当前
len遍历数组，合并相邻两个段 - 每次合并后将结果写回原数组
A
⚠️ 注意处理边界情况，比如最后一个段可能不足 len 个元素
时间复杂度分析
整个算法的时间复杂度为 **O(n × log n)**：
- 外层循环执行次数为 log n（因为每次
len翻倍） - 内层每次遍历整个数组，时间复杂度为 O(n)
- 合并操作总和为 O(n)，因此整体为 O(n × log n)
4. 示例演示
我们以一个数组为例来演示迭代归并排序的过程：
初始数组：
[6, 2, 5, 1, 4, 3]
第一步：合并相邻的单个元素
- 合并 [6, 2] → [2, 6]
- 合并 [5, 1] → [1, 5]
- 合并 [4, 3] → [3, 4]
此时数组变为：
[2, 6, 1, 5, 3, 4]
第二步：合并相邻的两个元素
- 合并 [2, 6] 和 [1, 5] → [1, 2, 5, 6]
- 合并 [3, 4] → 保持不变
此时数组变为：
[1, 2, 5, 6, 3, 4]
第三步：合并相邻的四个元素
- 合并 [1, 2, 5, 6] 和 [3, 4] → [1, 2, 3, 4, 5, 6]
最终排序完成 ✅
5. 递归 vs 迭代
| 对比维度 | 递归实现 | 迭代实现 |
|---|---|---|
| 代码简洁性 | ✅ 简洁易懂 | ❌ 稍复杂 |
| 性能 | ❌ 有递归调用开销 | ✅ 更快 |
| 内存占用 | ❌ 使用栈空间 | ✅ 更省 |
| 可调试性 | ✅ 易调试 | ❌ 稍难 |
| 适用场景 | 小数组或教学 | ✅ 大数组或性能敏感场景 |
✅ 推荐：在实际开发中优先使用迭代实现，尤其在对性能敏感的场景下
6. 总结
本教程我们介绍了归并排序的迭代实现方式：
- 首先回顾了归并排序的基本原理和递归实现
- 然后详细讲解了迭代实现的思路与实现步骤
- 提供了合并函数和完整排序函数的伪代码
- 通过一个数组排序示例帮助理解其工作流程
- 最后对比了递归与迭代实现的优劣，并给出了使用建议
归并排序的迭代实现虽然代码稍复杂，但在性能和内存使用上更优，适合实际项目中使用。