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