前言
非递归实现的归并排序通常被称为'自底向上'（Bottom-Up）策略。与递归版本先将数组对半拆分直到只剩一个元素再回溯合并不同，非递归版本直接从最小的子数组（长度为 1）开始，两两合并，然后步长翻倍（2, 4, 8...），直到整个数组有序。
核心思路
将递归转换为非递归主要有两种路径：用栈模拟递归过程，或者直接改写为循环结构。但在归并排序中，单纯用栈模拟往往只能做到拆分，难以在弹出时准确找回合并指令。因为一旦区间被拆分压栈，原区间的合并上下文就丢失了，程序不知道这两个子区间原本是'兄弟'关系。
因此，我们采用循环结构。核心在于控制步长（gap）：
- 初始 gap = 1，将数组视为 N 个长度为 1 的有序子数组。
- 相邻两个长度为 1 的子数组合并成长度为 2 的有序子数组。
- gap 翻倍为 2，继续合并成长度为 4 的有序子数组。
- 重复此过程，直到 gap 超过数组长度。
想象面前有一排乱序的扑克牌，先两两整理成有序的 2 张一组，再把这些组两两整理成 4 张一组，以此类推，直到整副牌有序。
实现流程演示
假设数组为 [10, 6, 7, 1, 3, 9, 4, 2]，我们可以观察循环如何控制归并过程。
第一轮：gap = 1
此时每 1 个元素为一组进行两两合并。
[10]和[6]合并 ->[6, 10][7]和[1]合并 ->[1, 7][3]和[9]合并 ->[3, 9][4]和[2]合并 ->[2, 4]
数组变为两两有序：[6, 10, 1, 7, 3, 9, 2, 4]。
第二轮：gap = 2
此时每 2 个元素为一组进行合并。
[6, 10]和[1, 7]合并 ->[1, 6, 7, 10][3, 9]和[2, 4]合并 ->[2, 3, 4, 9]
数组变为四四有序：[1, 6, 7, 10, 2, 3, 4, 9]。
第三轮：gap = 4
最后将左右两部分合并。
[1, 6, 7, 10]和[2, 3, 4, 9]合并 ->[1, 2, 3, 4, 6, 7, 9, 10]
至此，数组完全有序。
边界问题的处理
归并排序的逻辑基于'完全二叉树'，理想情况下每一步都能完美均分。但当数组长度不是 2 的整数次幂时，会出现边界问题。
例如长度为 10 的数组，在 gap = 2 时，最后会剩下一个长度为 2 的子数组无法配对；gap = 4 时，最后剩下长度为 2 的部分。这些落单的元素或不对等的区间需要特殊处理。
主要涉及四个边界变量：begin1, end1（左区间起点终点）和 begin2, end2（右区间起点终点）。其中只有 begin1 是绝对安全的，其余三个都可能越界。
解决方案分为两种情况：
- 数组落单：如果
begin2 >= n，说明当前左子数组后面没有对应的右子数组了，直接跳过本次循环，无需归并。 - 长度不等：如果 ，说明右区间超出了数组范围，需要将 修正为 ，确保只合并有效部分。
