排序算法之：块内插入与块外归并的混合排序（Block Insertion-Merge Sort）

题目描述

我们有一个长度为 \(n\) 的数组 arr，现在需要将其从小到大排序。
已知数组整体是“部分有序”的，即它由若干个内部有序的“块”（block）组成，但这些块的顺序是混乱的。例如：

[5, 6, 7, 1, 2, 9, 10, 3, 4, 8]

可以看作三个有序块：

1. [5, 6, 7]
2. [1, 2, 9, 10]
3. [3, 4, 8]

设计一个高效的排序算法，利用“块内有序、块间无序”的特性，尽可能降低比较和移动的次数。

解题过程

步骤 1：问题抽象与目标分析

如果数组完全随机，常规 \(O(n \log n)\) 排序算法（如快速排序、归并排序）是高效的。
但若数组已经部分有序（尤其是由多个有序块组成），我们可以设计一个两阶段算法：

1. 块识别：找出所有内部有序的连续子数组（块）。
2. 块合并：利用类似归并排序的方法，将这些块逐步合并成一个完整的有序数组。

目标是利用已有有序信息，减少不必要的比较和交换，使算法在部分有序的情况下比通用排序算法更快。

步骤 2：块识别策略

我们需要扫描数组，识别出每个有序块的起始和结束位置。
定义：一个“有序块”是最大的连续子数组，其中每个元素都 ≤ 下一个元素（非严格递增）。

具体做法：

• 设置指针 start = 0。
• 从 start 开始，向右遍历，直到遇到 arr[i] > arr[i+1] 或到达数组末尾，此时 i 就是当前块的结束位置。
• 记录块区间 [start, end]，然后更新 start = end + 1，继续扫描。

例如数组 [5, 6, 7, 1, 2, 9, 10, 3, 4, 8]：

• 第一块：从索引 0 到 2（因为 7 > 1）。
• 第二块：从索引 3 到 6（因为 10 > 3）。
• 第三块：从索引 7 到 9。

时间复杂度：一次扫描 \(O(n)\)，每个元素只被访问一次。

步骤 3：块合并策略

识别出多个有序块后，我们需要将它们合并成一个有序数组。
这本质上是一个多路归并（K-way merge）问题。

基本思路：

1. 使用一个最小堆（优先队列），初始时放入每个块的第一个元素及其块索引。
2. 每次从堆中弹出最小元素，放入结果数组，并从该元素所在的块中取出下一个元素（如果块非空）放入堆中。
3. 重复直到所有块为空。

但是，如果我们想原地排序（不使用额外 \(O(n)\) 的结果数组），则需要更巧妙的合并方法。

步骤 4：原地合并两个有序块

假设我们有两个相邻的有序块 A 和 B，它们原本在数组中连续存放。
我们可以使用“原地归并”的方法合并它们，常见方法有：

• 双指针+移位：类似插入排序，但可以批量移动。
• 旋转交换：找到 A 中第一个大于 B[0] 的位置，将 B 整体旋转到 A 之前。

例如：

块1: [5, 6, 7]
块2: [1, 2, 9, 10]
合并时，我们发现 1 比 5 小，所以将块2整体移到块1前面。

具体操作可用三次反转法（旋转数组）实现，但需注意块长度不同时的效率。

步骤 5：整体合并顺序

多个块合并时，可以借鉴归并排序的分治思想：

1. 将相邻的两个块合并，形成更大的有序块。
2. 重复这一过程，直到只剩一个块。

为了最小化合并代价，我们可以采用类似哈夫曼合并的策略（优先合并长度较小的块），但简单实现通常采用顺序两两合并。

例如：

初始块：[块0, 块1, 块2]
第一步：合并块0和块1 → 新块A
第二步：合并新块A和块2 → 最终有序数组

步骤 6：算法步骤总结

1. 扫描识别块：
   遍历数组，记录每个有序块的起始位置，存入列表 blocks（每个元素为 (start, end)）。
2. 初始化合并：
   若 blocks 只有一个块，说明数组已经有序，直接返回。
3. 循环合并相邻块：

   while 块数量 > 1:
       新建列表 new_blocks
       for i in range(0, len(blocks), 2):
           if i+1 < len(blocks):
               合并 blocks[i] 和 blocks[i+1] → 新的大块
               记录新块区间到 new_blocks
           else:
               将 blocks[i] 直接加入 new_blocks
       blocks = new_blocks
   

4. 原地合并函数（关键）：
   • 输入两个相邻区间 [l, m] 和 [m+1, r]（分别有序）。
   • 使用双指针 i = l, j = m+1。
   • 若 arr[i] <= arr[j]，则 i++，该元素已就位。
   • 否则，将 arr[j] 插入到 i 之前：
     • 找到 j 的连续段（arr[j..k] 均小于 arr[i]）。
     • 将子数组 arr[i..m] 向右移动 (k-j+1) 位。
     • 将 arr[j..k] 放到 i 之前。
     • 更新指针和区间边界。
   • 继续直到 j > r。
     （此方法在块间逆序少时接近 \(O(n)\)，最坏 \(O(n^2)\)，但实际部分有序时效率高。）

步骤 7：时间复杂度分析

• 块识别：\(O(n)\)。
• 合并：
  设初始有 \(k\) 个块，平均长度为 \(n/k\)。
  每次合并两个块，最坏比较次数为两长度之和。
  若采用简单的两两顺序合并（类似归并排序的合并树），总比较次数约为 \(n \log k\)（因为合并树高度 \(\log k\)，每层总比较 \(O(n)\)）。
  由于 \(k\) 通常远小于 \(n\)，因此比完整归并排序（比较 \(n \log n\) 次）更优。
  在数组完全有序时 \(k=1\)，算法退化为 \(O(n)\)；完全逆序时 \(k=n\)，退化为 \(O(n \log n)\)。

步骤 8：示例演示

输入：arr = [5, 6, 7, 1, 2, 9, 10, 3, 4, 8]

1. 扫描识别块：
   • 块0: [0,2] → [5,6,7]
   • 块1: [3,6] → [1,2,9,10]
   • 块2: [7,9] → [3,4,8]
2. 合并块0和块1：
   • 比较 5 和 1 → 1 移到最前，整体右移 [5,6,7] → [1,5,6,7,2,9,10]
   • 继续比较 5 和 2 → 2 插入到 5 前 → [1,2,5,6,7,9,10]
   • 块1剩余 [9,10] 均大于 7，直接拼接 → [1,2,5,6,7,9,10]
     新块A: [0,6] 有序。
3. 合并块A和块2([3,4,8])：
   • 类似过程，得到最终有序数组 [1,2,3,4,5,6,7,8,9,10]。

总结

块内插入与块外归并的混合排序利用了数组的部分有序性：

1. 识别有序块（一次扫描）。
2. 通过类似归并的方式合并这些块（原地或使用辅助空间）。
3. 在块间逆序较少时，算法接近 \(O(n)\)；在最坏情况下仍保持 \(O(n \log n)\)。

这种算法在现实数据（如日志文件按时间戳大致有序、部分排序后的数据）中表现优异，是一种自适应的混合排序策略。