前言
非递归实现归并排序，通常被称为'自底向上'（Bottom-Up）的归并排序。与递归版本不同，非递归版本直接从最小的子数组（长度为 1）开始，两两合并，然后长度翻倍（2, 4, 8 ...），直到合并完整个数组。
一、归并排序非递归的核心思路
递归算法转换为非递归实现主要有两种常见方法：使用栈结构模拟递归过程，或将递归逻辑改写为循环结构。
1.1 栈模拟失效
如果仅通过栈结构模拟递归过程，只能够做到拆分数组，而不能做到合并数组。因为拆分后的区间被丢弃，无法回溯执行合并操作。
假设我们要排序数组 arr = [8, 4, 5, 7]。 初始状态：栈中有任务 [0, 3]。 第一步：弹出 [0, 3]。计算 mid = 1。拆分为左 [0, 1] 和右 [2, 3]。将 [2, 3] 和 [0, 1] 压入栈。关键点：[0, 3] 被彻底扔了，没人记得原本是要合并这俩段。 后续：栈里剩下的 [2, 3] 也会经历同样的命运，被拆解成单元素后被遗忘。此时 [0, 0] 和 [1, 1] 都处理完了，按理说应该执行 merge(0, 0, 1)，但是栈里没有这个指令。
1.2 循环结构实现
递归版本是'先拆分，后合并'，而非递归版本则是直接从最小的子数组开始'只合并'，不需要拆分。
核心原理如下：
- 步长（gap）设为 1：首先将数组看作由 N 个长度为 1 的有序子数组组成。
- 两两合并：相邻的两个长度为 1 的子数组合并成长度为 2 的有序子数组。
- 步长翻倍：将步长设为 2，相邻的两个长度为 2 的子数组合并成长度为 4 的有序子数组。
- 重复：步长继续翻倍（4, 8, 16...），直到步长超过数组长度，此时整个数组就有序了。
简单理解：想象面前有一排乱序的扑克牌。步长=1：先把相邻的每 1 张牌看作一组，两两合并成有序的 2 张牌。步长=2：再把相邻的每 2 张牌看作一组，两两合并成有序的 4 张牌。循环直到步长超过数组长度，排序完成。
二、归并排序非递归的实现流程
假设存在如下数组 [10, 6, 7, 1, 3, 9, 4, 2]，演示循环结构是如何控制归并过程的。
2.1 核心变量回顾
- gap: 当前子序列的长度
- 左数组区间：[begin1, end1]
- 右数组区间：[begin2, end2]
2.2 核心流程展示
第一轮：gap=1
- 第一次合并：左子数组 [0,0]={10}，右子数组 [1,1]={6}。6 小于 10，交换位置。结果：[6, 10, 7, 1, 3, 9, 4, 2]
- 第二次合并：左子数组 [2,2]={7}，右子数组 [3,3]={1}。1 小于 7，交换位置。结果：[6, 10, 1, 7, 3, 9, 4, 2]
- 第三次合并：左子数组 [4,4]={3}，右子数组 [5,5]={9}。3 小于 9，无需变动。结果：[6, 10, 1, 7, 3, 9, 4, 2]
- 第四次合并：左子数组 [6,6]={4}，右子数组 [7,7]={2}。2 小于 4，交换位置。第一轮结束，数组变为两两有序：[6, 10, 1, 7, 3, 9, 2, 4]
第二轮：gap=2
- 第一次归并：左子数组 [0,1]={6,10}，右子数组 [2,3]={1,7}。比较 6 和 1 -> 取 1；比较 6 和 7 -> 取 6；比较 10 和 7 -> 取 7；剩下 10 -> 取 10。结果：[1, 6, 7, 10, 3, 9, 2, 4]
- 第二次归并：左子数组 [4,5]={3,9}，右子数组 [6,7]={2,4}。比较 3 和 2 -> 取 2；比较 3 和 4 -> 取 3；比较 9 和 4 -> 取 4；剩下 9 -> 取 9。结果：[1, 6, 7, 10, 2, 3, 4, 9] 第二轮结束，数组变为四四有序：[1, 6, 7, 10, 2, 3, 4, 9]
第三轮：gap=4
- 第一次归并：左子数组 [0,3]={1, 6, 7, 10}，右子数组 [4,7]={2, 3, 4, 9}。依次比较合并。结果：[1, 2, 3, 4, 6, 7, 9, 10] 第三轮结束，数组完全有序。
三、归并排序非递归的疑难点
3.1 满足左右数组均分
归并排序的逻辑结构是基于'完全二叉树'，当满足每一步都能凑齐完美的'左半边'和'右半边'。例如步长 1、2、4、8 时，若数组长度为 8，均为完美分割。
