目录
我们来深入探讨另一个经典的高效排序算法。这次我们不使用递归，而是用一种自底向上的迭代方式来构建归并排序 (Iterative Merge Sort)。
排序问题的“逆向思维”
我们之前讨论的所有排序算法，无论是 O(n^2) 的还是快速排序，其思路都是“自顶向下”的：
面对一个大问题（排序整个数组），我们通过交换、插入或分割等方式，逐步将其理顺或分解成小问题。
归并排序则采用一种“自底向上”的逆向思维。它始于一个非常美妙的洞察： 一个只包含一个元素的数组，天然就是有序的。
基于这个起点，我们提出一个问题：
如果我们有两个已经有序的子数组，我们能否用一种非常高效的方式将它们合并成一个更大的有序数组？
✅答案是肯定的，这个过程就是归并排序的原子操作——合并 (Merge)。如果我们能完美地实现 Merge 操作，那么整个排序问题就转化为：
将原始数组看作
n个长度为1的有序子数组。两两合并，得到
n/2个长度为2的有序子数组。再对这些长度为2的子数组两两合并，得到
n/4个长度为4的有序子数组。持续这个过程，直到最后只剩下一个长度为
n的有序数组。
这个过程就像搭积木，从最小的有序单元开始，一层一层地构建出最终的有序整体。这就是迭代式归并排序的第一性原理。
核心操作 Merge (合并)
我们必须先完美地解决“如何合并两个有序子数组”这个问题。
📌 目标：给定数组 arr，其中 arr[l...m] 和 arr[m+1...r] 这两段各自已经有序，我们要将它们合并，使得 arr[l...r] 整体有序。
策略（双指针法）：
因为我们需要在原数组 arr 上进行修改，直接操作会丢失数据。所以，我们必须创建两个临时的辅助数组，比如 L[] 和 R[]，分别用来存放 arr[l...m] 和 arr[m+1...r] 的内容。
设置三个指针：i 指向 L[] 的头部，j 指向 R[] 的头部，k 指向原数组 arr 的 l 位置（这是我们将要填充的起始位置）。
比较 L[i] 和 R[j] 的值：
如果
L[i]<=R[j]，就将L[i]的值赋给arr[k]，然后i和k各向前走一步。如果 R
[j]<=L[i]，就将R[j]的值赋给arr[k]，然后j和k各向前走一步。
重复第比较过程，直到 L[] 或 R[] 中的一个数组被完全遍历完（i 或 j 到达了数组末尾）。
此时，另一个数组中必然还有剩余的元素，因为它们已经是有序的，且都比已合并的所有元素要大，所以直接按顺序将它们全部复制到 arr 的末尾即可。
这个 Merge 操作是整个算法的基石。
代码的逐步完善
第一阶段：实现 merge 辅助函数
根据上面的推导，我们先构建这个核心的辅助函数。
#include <iostream>
// 合并 arr[l...m] 和 arr[m+1...r]
void merge(int arr[], int l, int m, int r) {
// 1. 计算左右两个子数组的大小
int n1 = m - l + 1;
int n2 = r - m;
// 2. 创建临时数组
int L[n1], R[n2];
// 3. 将数据复制到临时数组 L[] 和 R[]
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// 4. 合并临时数组回到 arr[l...r]
int i = 0; // L[] 的初始索引
int j = 0; // R[] 的初始索引
int k = l; // 合并后数组的初始索引
while (i < n1 && j < n2) {
if (L[i] <= R[j]) { // 为了稳定性，使用 <=
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 5. 复制 L[] 中剩余的元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 6. 复制 R[] 中剩余的元素
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}注意：在C++中直接使用 int L[n1] 这种变长数组（VLA）是G++编译器的扩展，不是标准C++。在严格的标准C++或某些编译器（如MSVC）下，你需要使用动态内存分配 new int[n1] 并记得 delete[]。但为了教学和简洁，我们这里暂时使用VLA。
第二阶段：构建迭代框架（外层循环）
现在我们有了 merge 工具，可以开始搭建排序的框架了。我们需要一个外层循环，它控制着我们正在合并的“有序子数组”的大小。这个大小从1开始，每次翻倍。
// 迭代式归并排序主函数
void mergeSort(int arr[], int n) {
int curr_size; // 当前合并的子数组大小 (1, 2, 4, 8...)
int left_start; // 每一对要合并的子数组的起始位置
// 外层循环：子数组的大小从1开始，每次翻倍
for (curr_size = 1; curr_size <= n - 1; curr_size = 2 * curr_size) {
// 内层循环将遍历数组，对 curr_size 大小的子数组进行两两合并
}
}第三阶段：实现内层循环和边界计算
内层循环负责在数组中移动，依次选取要合并的每一对子数组。left_start 是每一对的起点。
由于我们每次处理 2 * curr_size 这么大的一块区域，所以 left_start 的步长就是 2 * curr_size。
这里最棘手的是处理边界情况，特别是当数组末尾不足以凑成完整的一对子数组时。
// 因为不能用STL，我们自己实现一个简单的min函数
int min(int x, int y) { return (x < y) ? x : y; }
void mergeSort(int arr[], int n) {
int curr_size;
int left_start;
for (curr_size = 1; curr_size <= n - 1; curr_size = 2 * curr_size) {
// 内层循环：选取要合并的子数组的起始点
for (left_start = 0; left_start < n - 1; left_start += 2 * curr_size) {
// 1. 计算中间点和右边界
// 中间点是左边子数组的结束点
int mid = min(left_start + curr_size - 1, n - 1);
// 右边界是右边子数组的结束点
int right_end = min(left_start + 2 * curr_size - 1, n - 1);
// 2. 调用 merge 函数
// 我们需要合并 arr[left_start...mid] 和 arr[mid+1...right_end]
merge(arr, left_start, mid, right_end);
}
}
}void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
std::cout << arr[i] << " ";
std::cout << std::endl;
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
std::cout << "Original array: \n";
printArray(arr, n);
mergeSort(arr, n);
std::cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}复杂度与特性分析
时间复杂度 (Time Complexity)
归并排序的分析非常直观。我们看外层循环：
curr_size依次取1, 2, 4, 8, ...，直到curr_size大于或等于n。这个过程循环了多少次？答案是 log_2n 次。所以我们共有 O(logn) 趟 (Pass)。
在每一趟中（例如当
curr_size=4时），内层循环和merge函数会把整个数组的所有元素都访问和移动一次。所以每一趟的成本是 O(n)。这个过程与数组的初始状态完全无关。无论数组是已经有序还是完全逆序，它都必须老老实实地执行这 logn 趟合并。
因此，归并排序的最好、最坏和平均情况的时间复杂度都是：O(nlogn)
空间复杂度 (Space Complexity)
这是归并排序最主要的“成本”所在。
回顾我们的
merge函数，在合并两个总大小为k的子数组时，我们需要创建大小为k的临时数组L和R。在每一趟合并中，最坏情况是合并两个大小为
n/2的数组，需要一个大小为n的临时空间。这个空间需求与输入规模
n成正比。因此，空间复杂度是：O(n)
它不是一个原地排序算法。
稳定性 (Stability)
稳定性的关键在于
merge函数中的比较if (L[i] <= R[j])。当我们遇到来自左边子数组和右边子数组的元素相等时，这个
L[i] <= R[j]条件会为真，我们会优先把左边子数组的元素（也就是在原始数组中排在前面的那个元素）放入合并后的数组中。这个简单的细节保证了相等元素的原始相对顺序不会被改变。
因此，归并排序是稳定的排序算法 (Stable Sort)。
归并排序是第一个我们学习到的时间复杂度稳定在 O(nlogn) 的算法，它没有快速排序那样的最坏情况。同时它还是稳定的。
这两个巨大的优点使它在很多场景下非常受欢迎，例如在需要稳定性的外部排序或链表排序中。它唯一的显著缺点就是需要 O(n) 的额外空间。