混合归并排序[易语言源码]

混合归并排序易语言源码混合归并排序原理
一句话概括
首趟扫描找自然段边界，后续轮次复用边界做归并，不再重新扫描。

三个阶段
1. 扫描自然段（只做一次，O(n)）

从左到右扫一遍数组，遇到 a > a[i+1] 就是一个”降序断点”，说明前面的自然升序段结束了。把每个段的起始下标存到 游标首[]，结束下标存到 游标尾_[]。

比如 [3,7,12, 5,9, 2, 6,8,15, 1,4,10] 一趟扫完，分段计数 = 5，每个段的边界都记录好了。

2. 快速判断（O(1)）

扫描完看分段计数：

分段计数 = 1 → 整个数组已经升序，直接返回
分段计数 = 个数 → 每个元素自成一档，说明完全降序，反转即可
这两个极端场景不用归并，白捡 O(n) 甚至 O(1) 的性能。

3. 多轮归并（核心循环）

每轮做的事：

合并循环：步长为 2 遍历分段，相邻两段调 子程序_合并4 做两路归并。落单的段（奇数个分段时最后那个）传 右首=0, 右尾=0，子程序检测到直接 内存拷贝 复制过去不合并。
边界更新循环：同样步长为 2，游标首[m1] = 游标首[n1]（新段头 = 左段头），游标尾_[m1] = 游标尾_[n1+1]（新段尾 = 右段尾）。落单的段尾就是它自己的尾。
分段计数变成 (分段计数+1) 2（大概减半）
局变_源是临时 取反，切换源/目标数组
4. 双缓冲交替写入

关键优化：不每轮全数组拷贝。用 参数_数组 和 临时_归并 两个数组交替当源和目标：

第1轮：原数组 → 临时数组
第2轮：临时数组 → 原数组
第3轮：原数组 → 临时数组
…
最后如果数据落在临时数组里，用 参数_数组 = 局变_临时_归并 一次性拷回。

和其他归并排序的区别
普通归并 自然归并 混合归并
初始分段 固定步长1 扫描自然段 扫描自然段
后续轮次 步长翻倍 重新扫描 复用边界
完全升序 O(n log n) O(n) O(n)
完全随机 O(n log n) O(n log n) + 扫描 O(n log n)
额外开销 无 每轮O(n)扫描 只1次扫描 + 边界数组
混合归并 = 自然归并的发现能力 + 普通归并的扫描效率。首趟扫描利用了数据的自然有序性（少段就少合并），后续轮次不再扫描又省掉了自然归并每轮 O(n) 的额外开销。