## 一、你给出的算法是什么

你描述的算法可以形式化为：

1. 把规模为 nn 的数组分成若干个**大小为 ⌊n⌋⌊n​⌋** 的子数组；
    
2. 对每个子数组**分别排序**；
    
3. 然后把这些有序子数组合并成一个整体有序数组。
    

也就是说，这是一个：

> **先分块排序，再多路归并**的分治算法。

注意：这和标准归并排序不同。标准归并排序是每次二分，递归到规模 1，再两两合并。  
你这里是先分成 nn​ 块，每块大小 nn​，排好序后再合并。

---

## 二、第一步：分块排序的代价

设：

k=⌊n⌋k=⌊n​⌋

每个子数组大小为 kk，子数组个数为：

m=⌈nk⌉=Θ(n)m=⌈kn​⌉=Θ(n​)

对每个子数组排序，使用归并排序，代价为：

O(klog⁡k)=O(nlog⁡n)O(klogk)=O(n​logn​)

所以所有子数组排序的总代价为：

m⋅O(klog⁡k)=Θ(n)⋅O(nlog⁡n)=O(nlog⁡n)m⋅O(klogk)=Θ(n​)⋅O(n​logn​)=O(nlogn​)

而：

log⁡n=12 log⁡nlogn​=21​logn

所以：

O(nlog⁡n)=O(nlog⁡n)O(nlogn​)=O(nlogn)

这一步是对的。

---

## 三、第二步：合并这些有序子数组

现在有 m=Θ(n)m=Θ(n​) 个有序子数组，需要合并成一个整体有序数组。

### 3.1 如果使用两两归并

最直接的方法是做多趟两两归并：

- 第一趟：nn​ 个有序段，两两合并，得到 n/2 n​/2 个有序段；
    
- 第二趟：n/4 n​/4 个有序段；
    
- …
    
- 直到只剩 1 个有序段。
    

每一趟都要扫描所有 nn 个元素，代价为 O(n)O(n)。  
一共有多少趟？

从 nn​ 个段合并到 1 个段，需要：

log⁡2(n)=12 log⁡2 nlog 2​(n​)=21​log 2​n

趟。

所以两两归并的总代价为：

O(n)⋅O(log⁡n)=O(nlog⁡n)=O(nlog⁡n)O(n)⋅O(logn​)=O(nlogn​)=O(nlogn)

### 3.2 如果使用堆做多路归并

也可以用最小堆做 mm 路归并：

- 堆中有 m=nm=n​ 个元素；
    
- 每次取出最小元素，再插入该段的下一个元素；
    
- 总共要取 nn 次；
    
- 每次堆操作代价 O(log⁡m)=O(log⁡n)=O(log⁡n)O(logm)=O(logn​)=O(logn)。
    

所以总代价：

O(nlog⁡m)=O(nlog⁡n)=O(nlog⁡n)O(nlogm)=O(nlogn​)=O(nlogn)

两种合并方式得到的总代价都是：

O(nlog⁡n)O(nlogn)

---

## 四、总复杂度

总时间 = 分块排序时间 + 合并时间

O(nlog⁡n)+O(nlog⁡n)=O(nlog⁡n)O(nlogn​)+O(nlogn​)=O(nlogn)

所以这个算法的整体复杂度仍然是：

O(nlog⁡n)O(nlogn)​

---

## 五、递归式怎么写

如果你要把这个算法写成递归式，可以这样写：

T(n)={Θ(1),n≤1,Θ(n)⋅T(n)⏟分块递归排序+Θ(nlog⁡n)⏟合并,n>1.T(n)=⎩⎨⎧​Θ(1),分块递归排序Θ(n​)⋅T(n​)​​+合并Θ(nlogn​)​​,​n≤1,n>1.​

但注意：这里每个子问题规模是 nn​，不是 n/2 n/2。  
这已经不是标准归并排序的递归式了。

不过，如果你把“对每个子数组排序”看作直接调用标准排序，而不是继续递归分块，那么递归式就退化成：

T(n)=Θ(n)⋅O(nlog⁡n)+O(nlog⁡n)T(n)=Θ(n​)⋅O(n​logn​)+O(nlogn​)

也就是：

T(n)=O(nlog⁡n)T(n)=O(nlogn)

---

## 六、这个算法和标准归并排序的关系

|项目|标准归并排序|你的分块归并|
|---|---|---|
|划分方式|每次二分，规模 n/2 n/2|分成 nn​ 块，每块大小 nn​|
|递归式|T(n)=2 T(n/2)+Θ(n)T(n)=2 T(n/2)+Θ(n)|T(n)=Θ(n)T(n)+Θ(nlog⁡n)T(n)=Θ(n​)T(n​)+Θ(nlogn​)|
|递归深度|Θ(log⁡n)Θ(logn)|Θ(log⁡log⁡n)Θ(loglogn) 或直接一层|
|每层合并代价|Θ(n)Θ(n)|Θ(nlog⁡n)Θ(nlogn​)|
|总复杂度|Θ(nlog⁡n)Θ(nlogn)|O(nlog⁡n)O(nlogn)|

所以：

- 你的分块归并**最终上界也是 O(nlog⁡n)O(nlogn)**；
    
- 但它的递归结构、每层代价、递归深度都和标准归并排序不同；
    
- 它并不是“标准归并排序的递归树分析”。
    

---

## 七、最终结论

如果严格按照你给出的“分成 ⌊n⌋⌊n​⌋ 大小的子数组，分别排序，再归并”来分析：

T(n)=O(nlog⁡n)T(n)=O(nlogn)​

推导过程是：

1. 有 Θ(n)Θ(n​) 个子数组；
    
2. 每个子数组大小 Θ(n)Θ(n​)，排序代价 O(nlog⁡n)O(n​logn​)；
    
3. 分块排序总代价 O(nlog⁡n)=O(nlog⁡n)O(nlogn​)=O(nlogn)；
    
4. 合并这些有序子数组代价 O(nlog⁡n)=O(nlog⁡n)O(nlogn​)=O(nlogn)；
    
5. 总代价 O(nlog⁡n)O(nlogn)。

## 一、分块排序 + 多路归并的整体框架

### 1.1 算法步骤

设数组长度为 nn，令 k=⌊n⌋k=⌊n​⌋。

**步骤 1：划分**  
将数组划分为 kk 个子数组，每个子数组大小约为 kk：

A=[A 1,A 2,…,Ak],∣Ai∣≈k=⌊n⌋A=[A 1​,A 2​,…,Ak​],∣Ai​∣≈k=⌊n​⌋

**步骤 2：子数组内部排序**  
对每个子数组 AiAi​ 进行内部排序，得到有序子数组 Ai′Ai′​。

**步骤 3：多路归并**  
将 kk 个有序子数组 A 1′,A 2′,…,Ak′A 1′​,A 2′​,…,Ak′​ 合并为一个有序数组。

---

### 1.2 是否为多路归并？

✅ **是的。**

合并阶段需要同时处理 k=⌊n⌋k=⌊n​⌋ 个有序序列，这属于**多路归并**（Multiway Merge）。它是标准二路归并的推广：二路归并每次合并 2 个序列，而这里每次合并 kk 个序列。

---

## 二、子数组排序算法对复杂度的影响

### 2.1 若使用 O(m log m) 的排序算法（快排/归并/堆排）

单个子数组大小 m=⌊n⌋m=⌊n​⌋，排序时间为：

T 单块=O(mlog⁡m)=O(nlog⁡n)T 单块​=O(mlogm)=O(n​logn​)

共有 k=nk=n​ 个子数组，排序阶段总时间：

T 排序=k⋅O(nlog⁡n)=O(n⋅nlog⁡n)=O(nlog⁡n)T 排序​=k⋅O(n​logn​)=O(n​⋅n​logn​)=O(nlogn​)

化简：

O(nlog⁡n)=O(n⋅12 log⁡n)=O(nlog⁡n)O(nlogn​)=O(n⋅21​logn)=O(nlogn)

### 2.2 若使用 O(m²) 的排序算法（冒泡/选择/插入）

单个子数组排序时间：

T 单块=O(m 2)=O((n)2)=O(n)T 单块​=O(m 2)=O((n​)2)=O(n)

共有 k=nk=n​ 个子数组，排序阶段总时间：

T 排序=k⋅O(n)=O(n⋅n)=O(n 1.5)T 排序​=k⋅O(n)=O(n​⋅n)=O(n 1.5)

> **关键点**：单个子数组排序确实是 O(n)O(n)，但乘以子数组数量 nn​ 后，总排序阶段变成 O(n 1.5)O(n 1.5)，反而比 O(nlog⁡n)O(nlogn) 更差。

### 2.3 对比表

|子数组排序算法|单块时间|排序阶段总时间|合并阶段|总时间复杂度|
|---|---|---|---|---|
|快排/归并/堆排|O(nlog⁡n)O(n​logn​)|O(nlog⁡n)O(nlogn)|O(nlog⁡n)O(nlogn)|O(nlog⁡n)O(nlogn)​|
|冒泡/选择/插入|O(n)O(n)|O(n 1.5)O(n 1.5)|O(nlog⁡n)O(nlogn)|O(n 1.5)O(n 1.5)​|

---

## 三、合并阶段：多路归并的时间复杂度

使用**最小堆**实现 kk 路归并：

- 堆的大小为 k=nk=n​；
    
- 每个元素入堆、出堆各一次，每次堆操作 O(log⁡k)O(logk)；
    
- 总共有 nn 个元素。
    

合并阶段总时间：

T 合并=O(nlog⁡k)=O(nlog⁡n)=O(nlog⁡n)T 合并​=O(nlogk)=O(nlogn​)=O(nlogn)

---

## 四、二路归并排序的时间复杂度推导

### 4.1 算法递推关系

二路归并排序的步骤：

1. **分解**：将数组分成两半，时间 O(1)O(1)；
    
2. **解决**：递归排序两个子数组，时间 2 T(n/2)2 T(n/2)；
    
3. **合并**：合并两个有序数组，时间 O(n)O(n)。
    

递推关系：

T(n)=2 T(n 2)+O(n)T(n)=2 T(2 n​)+O(n)

### 4.2 递归树法

展开递归树：

|层|子问题数|每个子问题规模|该层合并代价|
|---|---|---|---|
|第 0 层|1|n|O(n)|
|第 1 层|2|n/2|2·O(n/2) = O(n)|
|第 2 层|4|n/4|4·O(n/4) = O(n)|
|…|…|…|…|
|第 i 层|2 ^i|n/2 ^i|2^ i·O(n/2^ i) = O(n)|
|…|…|…|…|
|第 log₂n 层|n|1|n·O(1) = O(n)|

**树的深度**：从 n 减半到 1，共 log⁡2 nlog 2​n 层。

**每层代价**：均为 O(n)O(n)。

总时间：

T(n)=O(n)+O(n)+⋯+O(n)⏟log⁡2 n 项=O(nlog⁡n)T(n)=log 2​n 项 O(n)+O(n)+⋯+O(n)​​=O(nlogn)

### 4.3 主定理验证

递推式 T(n)=2 T(n/2)+O(n)T(n)=2 T(n/2)+O(n) 符合主定理形式：

T(n)=aT(nb)+f(n),a=2, b=2, f(n)=O(n)T(n)=aT(bn​)+f(n),a=2, b=2, f(n)=O(n)

计算：

nlog⁡ba=nlog⁡22=n 1=nnlogb​a=nlog 2​2=n 1=n

比较 f(n)f(n) 与 nlog⁡banlogb​a：

f(n)=O(n)=Θ(nlog⁡ba)f(n)=O(n)=Θ(nlogb​a)

属于主定理**情形 2**，因此：

T(n)=Θ(nlog⁡balog⁡n)=Θ(nlog⁡n)T(n)=Θ(nlogb​alogn)=Θ(nlogn)

### 4.4 合并操作的具体代价

合并两个长度分别为 n 1 n 1​ 和 n 2 n 2​ 的有序数组：

- 需要遍历所有元素；
    
- 合并时间：
    

Tmerge=O(n 1+n 2)Tmerge​=O(n 1​+n 2​)

在二路归并中 n 1=n 2=n/2 n 1​=n 2​=n/2：

Tmerge=O(n/2+n/2)=O(n)Tmerge​=O(n/2+n/2)=O(n)

### 4.5 空间复杂度

归并排序需要辅助数组存储合并结果：

S(n)=O(n)S(n)=O(n)

---

## 五、二路归并 vs 多路归并对比

### 5.1 k 路归并的递推关系

将数组分成 kk 份，每份大小 n/kn/k：

T(n)=kT(nk)+O(nlog⁡k)T(n)=kT(kn​)+O(nlogk)

其中 O(nlog⁡k)O(nlogk) 是合并 kk 个有序序列（用最小堆）的代价。

### 5.2 求解

设 n=kmn=km，则递归深度 m=log⁡knm=logk​n。展开：

T(n)=nlog⁡k⋅log⁡kn=nlog⁡k⋅log⁡nlog⁡k=nlog⁡nT(n)=nlogk⋅logk​n=nlogk⋅logklogn​=nlogn

即：

T(n)=O(nlog⁡n)T(n)=O(nlogn)

### 5.3 对比表

|类型|递推关系|合并代价|总时间复杂度|
|---|---|---|---|
|二路归并|T(n)=2 T(n/2)+O(n)T(n)=2 T(n/2)+O(n)|O(n)O(n)|O(nlog⁡n)O(nlogn)|
|k 路归并|T(n)=kT(n/k)+O(nlog⁡k)T(n)=kT(n/k)+O(nlogk)|O(nlog⁡k)O(nlogk)|O(nlog⁡n)O(nlogn)|

**结论**：无论几路归并，只要分治平衡、合并高效，最终都是 O(nlog⁡n)O(nlogn)，与路数 kk 无关。

---

## 六、核心公式汇总

|项目|公式|
|---|---|
|子数组大小|m=⌊n⌋m=⌊n​⌋|
|子数组个数|k=⌊n⌋k=⌊n​⌋|
|O(m log m) 单块排序|O(nlog⁡n)O(n​logn​)|
|O(m log m) 排序阶段总时间|O(nlog⁡n)=O(nlog⁡n)O(nlogn​)=O(nlogn)|
|O(m²) 单块排序|O((n)2)=O(n)O((n​)2)=O(n)|
|O(m²) 排序阶段总时间|O(n⋅n)=O(n 1.5)O(n​⋅n)=O(n 1.5)|
|多路归并合并阶段|O(nlog⁡k)=O(nlog⁡n)=O(nlog⁡n)O(nlogk)=O(nlogn​)=O(nlogn)|
|二路归并递推|T(n)=2 T(n/2)+O(n)T(n)=2 T(n/2)+O(n)|
|二路归并结果|T(n)=O(nlog⁡n)T(n)=O(nlogn)|
|k 路归并递推|T(n)=kT(n/k)+O(nlog⁡k)T(n)=kT(n/k)+O(nlogk)|
|k 路归并结果|T(n)=O(nlog⁡n)T(n)=O(nlogn)|
|归并排序空间复杂度|S(n)=O(n)S(n)=O(n)|

---

## 七、核心结论

1. **划分成 ⌊√n⌋ 个块 + 多路归并** = 一种多路归并排序，合并阶段是 k=nk=n​ 路归并。
    
2. **子数组排序算法选择关键**：
    
    - O(mlog⁡m)O(mlogm) 类 → 总时间 O(nlog⁡n)O(nlogn)；
        
    - O(m 2)O(m 2) 类 → 单块 O(n)O(n)，但总排序阶段 O(n 1.5)O(n 1.5)，反而更差。
        
3. **二路归并时间复杂度**由递推 T(n)=2 T(n/2)+O(n)T(n)=2 T(n/2)+O(n) 推出，结果为 O(nlog⁡n)O(nlogn)​。
    
4. **多路归并**（k 路）合并代价 O(nlog⁡k)O(nlogk)，整体仍是 O(nlog⁡n)O(nlogn)​，与路数无关。
    
5. **空间复杂度**：归并类算法均为 O(n)O(n)。

## 5.1 二路归并排序（Python）

python

def merge_sort_ 2 way(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort_ 2 way(arr[:mid])
    right = merge_sort_ 2 way(arr[mid:])
    return merge_2 way(left, right)
def merge_2 way(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

## 5.2 多路归并排序（k-way，基于最小堆）

python

import heapq
def merge_sort_kway(arr, k=3):
    if len(arr) <= 1:
        return arr
    chunk_size = (len(arr) + k - 1) // k
    chunks = [
        merge_sort_kway(arr[i:i+chunk_size], k)
        for i in range(0, len(arr), chunk_size)
    ]
    return merge_kway(chunks)
def merge_kway(chunks):
    merged = []
    heap = []
    for i, chunk in enumerate(chunks):
        if chunk:
            heapq.heappush(heap, (chunk[0], i, 0))
    while heap:
        val, chunk_idx, elem_idx = heapq.heappop(heap)
        merged.append(val)
        if elem_idx + 1 < len(chunks[chunk_idx]):
            next_val = chunks[chunk_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, chunk_idx, elem_idx + 1))
    return merged

## 5.3 测试

python

import random
data = random.sample(range(100), 20)
print("原始数据:", data)
sorted_2 way = merge_sort_ 2 way(data.copy())
print("二路归并:", sorted_2 way)
sorted_3 way = merge_sort_kway(data.copy(), k=3)
print("三路归并:", sorted_3 way)
assert sorted_2 way == sorted_3 way == sorted(data), "排序结果错误！"

## 5.4 关键区别说明

|操作|二路归并|多路归并（k-way）|
|---|---|---|
|分治策略|每次分成 2 个子问题|每次分成 k 个子问题|
|合并方法|双指针线性合并|最小堆维护 k 个指针|
|时间复杂度|O(nlog⁡n)O(nlogn)|O(nlog⁡n)O(nlogn)（堆优化后相同）|
|空间复杂度|O(n)O(n)|O(n+k)O(n+k)|
|适用场景|内存排序|外部排序、海量数据|

## 5.5 堆优化原理

- 直接比较 kk 个子序列的当前元素需要 O(k)O(k)；
    
- 堆可以在 O(log⁡k)O(logk) 内找到最小值；
    
- 每轮合并复杂度从 O(nk)O(nk) 优化到 O(nlog⁡k)O(nlogk)。
    

堆中存储：

(current_value, chunk_index, element_index)(current_value, chunk_index, element_index)

## 5.6 外部排序扩展

处理大文件时：

1. 将数据分块写入临时文件；
    
2. 每次从 kk 个文件中读取一个块到内存缓冲区；
    
3. 用同样的堆策略合并，写入最终结果。
    

---

# 六、多路归并伪代码（算法导论风格）

## 6.1 MERGE-K

text

MERGE-K(A, p, r, k)
    n = r - p + 1
    chunk_size = ceil(n / k)
    let starts[0..k-1] and ends[0..k-1] be new arrays
    for i = 0 to k-1
        starts[i] = p + i * chunk_size
        ends[i] = min(p + (i + 1) * chunk_size - 1, r)
    let heap be a min-heap
    for i = 0 to k-1
        if starts[i] <= ends[i]
            heap.insert((A[starts[i]], i, starts[i]))
            starts[i] = starts[i] + 1
    let merged[0..n-1] be a new array
    for pos = 0 to n-1
        (min_val, i, idx) = heap.extract_min()
        merged[pos] = min_val
        if idx <= ends[i]
            heap.insert((A[idx + 1], i, idx + 1))
    for i = 0 to n-1
        A[p + i] = merged[i]

## 6.2 MERGE-SORT-K

text

MERGE-SORT-K(A, p, r, k)
    if p >= r
        return
    n = r - p + 1
    chunk_size = ceil(n / k)
    for i = 0 to k-1
        start = p + i * chunk_size
        end = min(p + (i + 1) * chunk_size - 1, r)
        MERGE-SORT-K(A, start, end, k)
    MERGE-K(A, p, r, k)

## 6.3 与二路归并的关键区别

|步骤|二路归并|多路归并|
|---|---|---|
|分治划分|分成 2 个子数组|分成 k 个子数组|
|合并策略|双指针线性合并|最小堆维护 k 个最小值|
|堆的使用|不需要|必须用堆|
|递归调用|固定 2 次|k 次|

## 6.4 Python 实现

python

import heapq
def merge_k(A, p, r, k):
    n = r - p + 1
    chunk_size = (n + k - 1) // k
    starts = [p + i * chunk_size for i in range(k)]
    ends = [min(p + (i + 1) * chunk_size - 1, r) for i in range(k)]
    heap = []
    for i in range(k):
        if starts[i] <= ends[i]:
            heapq.heappush(heap, (A[starts[i]], i, starts[i]))
            starts[i] += 1
    merged = []
    while heap:
        val, i, idx = heapq.heappop(heap)
        merged.append(val)
        if idx < ends[i]:
            heapq.heappush(heap, (A[idx + 1], i, idx + 1))
    for i in range(len(merged)):
        A[p + i] = merged[i]
def merge_sort_k(A, p, r, k=3):
    if p >= r:
        return
    n = r - p + 1
    chunk_size = (n + k - 1) // k
    for i in range(k):
        start = p + i * chunk_size
        end = min(p + (i + 1) * chunk_size - 1, r)
        merge_sort_k(A, start, end, k)
    merge_k(A, p, r, k)
A = [5, 2, 9, 1, 6, 3, 8, 4, 7]
merge_sort_k(A, 0, len(A) - 1, k=3)
print(A)

复杂度：

- 时间：O(nlog⁡n)O(nlogn)（与 k 无关）；
    
- 空间：O(n+k)O(n+k)。
    

---

# 七、Java 版多路归并排序及其 Python 改写

## 7.1 Java 原版

java

public class MultiWayMergeSort {
    public static void multiWayMergeSort(int[] arr, int left, int right, int k) {
        if (left < right) {
            int[] midPoints = new int[k - 1];
            for (int i = 0; i < k - 1; i++) {
                midPoints[i] = left + (right - left) * (i + 1) / k;
            }
            for (int i = 0; i < k; i++) {
                int subLeft = (i == 0) ? left : midPoints[i - 1] + 1;
                int subRight = (i == k - 1) ? right : midPoints[i];
                multiWayMergeSort(arr, subLeft, subRight, k);
            }
            merge(arr, left, midPoints, right);
        }
    }
    private static void merge(int[] arr, int left, int[] midPoints, int right) {
        // 省略
    }
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7, 8, 9, 1, 2};
        multiWayMergeSort(arr, 0, arr.length - 1, 3);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

## 7.2 Python 改写

python

import heapq
def multi_way_merge_sort(arr, left, right, k):
    if left < right:
        mid_points = []
        for i in range(1, k):
            mid_points.append(left + (right - left) * i // k)
        for i in range(k):
            sub_left = left if i == 0 else mid_points[i-1] + 1
            sub_right = right if i == k-1 else mid_points[i]
            multi_way_merge_sort(arr, sub_left, sub_right, k)
        merge(arr, left, mid_points, right)
def merge(arr, left, mid_points, right):
    starts = []
    ends = []
    starts.append(left)
    ends.append(mid_points[0] if len(mid_points) > 0 else right)
    for i in range(1, len(mid_points)):
        starts.append(mid_points[i-1] + 1)
        ends.append(mid_points[i])
    if len(mid_points) > 0:
        starts.append(mid_points[-1] + 1)
        ends.append(right)
    heap = []
    pointers = [start for start in starts]
    for i in range(len(starts)):
        if pointers[i] <= ends[i]:
            heapq.heappush(heap, (arr[pointers[i]], i))
            pointers[i] += 1
    merged = []
    while heap:
        val, i = heapq.heappop(heap)
        merged.append(val)
        if pointers[i] <= ends[i]:
            heapq.heappush(heap, (arr[pointers[i]], i))
            pointers[i] += 1
    for i in range(len(merged)):
        arr[left + i] = merged[i]
if __name__ == "__main__":
    arr = [12, 11, 13, 5, 6, 7, 8, 9, 1, 2]
    print("Original array:", arr)
    multi_way_merge_sort(arr, 0, len(arr)-1, 3)
    print("Sorted array: ", arr)

输出：

text

Original array: [12, 11, 13, 5, 6, 7, 8, 9, 1, 2]
Sorted array:  [1, 2, 5, 6, 7, 8, 9, 11, 12, 13]

关键点：

- 分治逻辑与原 Java 一致；
    
- 用 `heapq` 实现最小堆；
    
- 堆中存 `(value, subarray_index)`；
    
- 合并复杂度 O(nlog⁡k)O(nlogk)；
    
- 正确处理边界和不足 k 段的情况。
    

---

# 八、迭代版归并排序

## 8.1 你给出的代码

text

current_size = segment_size
while current_size < n
    for i = 0 to floor(n/(2*current_size))
        left = p + i * 2 * current_size
        mid = left + current_size - 1
        right = min(left + 2*current_size - 1, r)
        if mid < right
            MERGE(A, left, mid, right)
    current_size = current_size * 2

这是**非递归（迭代）版归并排序**，也叫自底向上的归并排序。

## 8.2 核心思想

- 初始子数组大小为 1；
    
- 两两合并相邻子数组；
    
- 子数组大小逐步翻倍：1 → 2 → 4 → 8 → …；
    
- 直到整个数组有序。
    

## 8.3 复杂度

- 每层合并 O(n)O(n)；
    
- 共 O(log⁡n)O(logn) 层；
    
- 总时间：
    

O(nlog⁡n)O(nlogn)

## 8.4 改成递归版

text

MERGE-SORT(A, p, r):
    if p < r:
        q = floor((p + r) / 2)
        MERGE-SORT(A, p, q)
        MERGE-SORT(A, q + 1, r)
        MERGE(A, p, q, r)

Python：

python

def merge_sort_recursive(A, p, r):
    if p < r:
        q = (p + r) // 2
        merge_sort_recursive(A, p, q)
        merge_sort_recursive(A, q + 1, r)
        merge(A, p, q, r)
def merge(A, p, q, r):
    nL = q - p + 1
    nR = r - q
    L = A[p:q+1]
    R = A[q+1:r+1]
    i = j = 0
    k = p
    while i < nL and j < nR:
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1
    while i < nL:
        A[k] = L[i]
        i += 1
        k += 1
    while j < nR:
        A[k] = R[j]
        j += 1
        k += 1

## 8.5 递归 vs 迭代

|特性|递归版|迭代版|
|---|---|---|
|实现方式|函数自我调用，分治|循环逐步合并|
|空间复杂度|O(log⁡n)O(logn) 栈空间|O(1)O(1) 额外空间|
|适用场景|代码简洁，教学|避免栈溢出，大规模数据|
|合并顺序|深度优先|广度优先（按层）|

## 8.6 多路归并的递归实现

python

def k_way_merge_sort(A, p, r, k):
    if p < r:
        chunk_size = (r - p + 1) // k
        mid_points = [p + (i+1)*chunk_size for i in range(k-1)]
        for i in range(k):
            sub_p = p if i == 0 else mid_points[i-1]
            sub_r = r if i == k-1 else mid_points[i] - 1
            k_way_merge_sort(A, sub_p, sub_r, k)
        merge_k(A, p, mid_points, r)

---

# 九、你的分块思路与标准归并排序的关系

你之前写过：

> 每个子数组大小为 ⌊n⌋⌊n​⌋，排序一个子数组的时间为 O(⌊n⌋log⁡⌊n⌋)O(⌊n​⌋log⌊n​⌋)。  
> 有 ⌊n⌋⌊n​⌋ 个子数组，总时间为 O(nlog⁡n)=O(nlog⁡n)O(nlogn​)=O(nlogn)。

这其实是一种**分块 + 多路归并**的思路，不是标准二路归并的递归树分析。

## 9.1 分块排序代价

设：

k=⌊n⌋k=⌊n​⌋

每个子数组大小 kk，子数组个数：

m=Θ(n)m=Θ(n​)

每个子数组排序：

O(klog⁡k)=O(nlog⁡n)O(klogk)=O(n​logn​)

所有子数组排序：

Θ(n)⋅O(nlog⁡n)=O(nlog⁡n)=O(nlog⁡n)Θ(n​)⋅O(n​logn​)=O(nlogn​)=O(nlogn)

## 9.2 合并代价

有 m=Θ(n)m=Θ(n​) 个有序子数组，需要合并。

### 两两归并

从 nn​ 个段合并到 1 个段，需要：

log⁡2(n)=12 log⁡2 nlog 2​(n​)=21​log 2​n

趟，每趟 O(n)O(n)，总代价：

O(nlog⁡n)=O(nlog⁡n)O(nlogn​)=O(nlogn)

### 堆做多路归并

堆大小 m=nm=n​，每次操作 O(log⁡m)=O(log⁡n)=O(log⁡n)O(logm)=O(logn​)=O(logn)，共 nn 次：

O(nlog⁡n)O(nlogn)

## 9.3 总复杂度

O(nlog⁡n)+O(nlog⁡n)=O(nlog⁡n)O(nlogn​)+O(nlogn​)=O(nlogn)

所以最终界仍是：

O(nlog⁡n)O(nlogn)​

## 9.4 与标准归并排序的区别

|项目|标准归并排序|分块归并|
|---|---|---|
|划分方式|每次二分，规模 n/2 n/2|分成 nn​ 块，每块 nn​|
|递归式|T(n)=2 T(n/2)+Θ(n)T(n)=2 T(n/2)+Θ(n)|T(n)=Θ(n)T(n)+Θ(nlog⁡n)T(n)=Θ(n​)T(n​)+Θ(nlogn​)|
|递归深度|Θ(log⁡n)Θ(logn)|一层或 Θ(log⁡log⁡n)Θ(loglogn)|
|每层合并代价|Θ(n)Θ(n)|Θ(nlog⁡n)Θ(nlogn​)|
|总复杂度|Θ(nlog⁡n)Θ(nlogn)|O(nlog⁡n)O(nlogn)|

结论：

- 分块归并最终上界也是 O(nlog⁡n)O(nlogn)；
    
- 但递归结构、每层代价、递归深度都与标准归并排序不同；
    
- 它不是标准归并排序的递归树分析，而是一种多路归并策略。
    

---

# 十、全局总结

## 10.1 标准归并排序

- 递归式：
    

T(n)=2 T(n/2)+Θ(n)T(n)=2 T(n/2)+Θ(n)

- 递归树每层代价 Θ(n)Θ(n)，共 Θ(log⁡n)Θ(logn) 层；
    
- 总时间：
    

Θ(nlog⁡n)Θ(nlogn)

## 10.2 多路归并排序

- 每次分成 kk 段；
    
- 树高：
    

O(log⁡kn)O(logk​n)

- 每层合并用堆：
    

O(nlog⁡k)O(nlogk)

- 总时间：
    

O(nlog⁡n)O(nlogn)

- 优势在外部排序：减少 I/O 轮次。
    

## 10.3 迭代版归并排序

- 自底向上，从大小 1 开始两两合并；
    
- 无递归栈；
    
- 总时间仍为 O(nlog⁡n)O(nlogn)。
    

## 10.4 递归 vs 迭代

- 递归：分治直观，深度优先；
    
- 迭代：广度优先，避免栈溢出。
    

## 10.5 你的分块思路

- 分成 nn​ 块，每块 nn​；
    
- 分别排序：O(nlog⁡n)O(nlogn)；
    
- 再合并：O(nlog⁡n)O(nlogn)；
    
- 总时间：O(nlog⁡n)O(nlogn)；
    
- 属于多路归并思路，不是标准二路归并递归树。
    

## 10.6 最终结论

无论是：

- 标准二路归并；
    
- 多路归并；
    
- 迭代归并；
    
- 分块归并；
    

最终时间复杂度都是：

O(nlog⁡n)O(nlogn)​

区别在于：

- 递归结构不同；
    
- 树高不同；
    
- 每层合并代价不同；
    
- 空间开销不同；
    
- 实际应用场景不同（内存排序 vs 外部排序）。
    

核心一句话：

> **归并排序的递归式 T(n)=2 T(n/2)+Θ(n)T(n)=2 T(n/2)+Θ(n) 得到 Θ(nlog⁡n)Θ(nlogn)；多路归并把它推广到 kk 路，总复杂度仍是 O(nlog⁡n)O(nlogn)，但通过降低树高减少了外部排序的 I/O 次数。**




# 一、标准归并排序（二分递归）

## 1.1 伪代码

text

MERGE(A, p, q, r)
    nL = q - p + 1
    nR = r - q
    let L[0 : nL - 1] and R[0 : nR - 1] be new arrays
    for i = 0 to nL - 1
        L[i] = A[p + i]
    for j = 0 to nR - 1
        R[j] = A[q + j + 1]
    i = 0
    j = 0
    k = p
    while i < nL and j < nR
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else
            A[k] = R[j]
            j = j + 1
        k = k + 1
    while i < nL
        A[k] = L[i]
        i = i + 1
        k = k + 1
    while j < nR
        A[k] = R[j]
        j = j + 1
        k = k + 1

text

MERGE-SORT(A, p, r)
    if p >= r
        return
    q = floor((p + r) / 2)
    MERGE-SORT(A, p, q)
    MERGE-SORT(A, q + 1, r)
    MERGE(A, p, q, r)

## 1.2 分治三步对应

|步骤|代码|作用|
|---|---|---|
|分解 Divide| `q = floor((p+r)/2)` |把数组分成左右两半|
|解决 Conquer| `MERGE-SORT(A,p,q)`、`MERGE-SORT(A,q+1,r)` |递归排序左右两半|
|合并 Combine| `MERGE(A,p,q,r)` |合并两个有序子数组|

## 1.3 递归式

T(n)=2 T(n/2)+Θ(n)=Θ(nlog⁡n)T(n)=2 T(n/2)+Θ(n)=Θ(nlogn)

递归树：

- 每层合并代价 Θ(n)Θ(n)；
    
- 共 Θ(log⁡n)Θ(logn) 层；
    
- 总代价 Θ(nlog⁡n)Θ(nlogn)。
    

---

# 二、题目要求的“分段归并排序”

题目要求：

> 将数组 a[0,…,n−1]a[0,…,n−1] 划分为 ⌊n⌋⌊n​⌋ 个子数组，每个子数组有 ⌊n⌋⌊n​⌋ 个元素。然后递归地对分割后的子数组进行排序，最后将所得到的子数组合并排序。

关键点：

1. 分段大小 k=⌊n⌋k=⌊n​⌋；
    
2. 子数组个数约为 ⌊n⌋⌊n​⌋；
    
3. 对每个子数组**递归地**排序；
    
4. 最后合并这些有序子数组。
    

这已经不是标准二路归并，而是**多路归并 + 分段递归**。

---

# 三、第一版分段归并伪代码

## 3.1 代码

text

MERGE-SORT-SQRT(A, p, r)
    n = r - p + 1
    if n <= 1
        return
    segment_size = floor(sqrt(n))
    if segment_size < 1
        segment_size = 1
    num_segments = floor(n / segment_size)
    if n % segment_size != 0
        num_segments = num_segments + 1
    for i = 0 to num_segments - 1
        start = p + i * segment_size
        end = min(p + (i+1)*segment_size - 1, r)
        MERGE-SORT-SQRT(A, start, end)
    current_size = segment_size
    while current_size < n
        for i = 0 to floor(n / (2*current_size))
            left = p + i * 2 * current_size
            mid = left + current_size - 1
            right = min(left + 2*current_size - 1, r)
            if mid < right
                MERGE(A, left, mid, right)
        current_size = current_size * 2

## 3.2 结构

- **分解**：按 ⌊n⌋⌊n​⌋ 分段；
    
- **解决**：对每段递归调用 `MERGE-SORT-SQRT`；
    
- **合并**：用 `while current_size < n` 自底向上合并。
    

## 3.3 问题

这段代码存在几个争议点：

1. **递归分解是否真的分成了 ⌊n⌋⌊n​⌋ 个子问题？**
    
2. **合并为什么不是像标准归并那样一句 `MERGE(A,p,q,r)`，而要写自底向上循环？**
    
3. **能不能改成“隐式递归合并”，让合并也像标准归并那样自然？**
    

材料中对这些问题做了大量讨论。

---

# 四、递归分解到底分成了几个子问题？

## 4.1 表面看

第一层：

n→⌊n⌋ 段 n→⌊n​⌋ 段

每段大小约为：

⌊n⌋⌊n​⌋

所以第一层确实分成了约 ⌊n⌋⌊n​⌋ 个子问题。

## 4.2 但递归进入子问题后

子数组长度变成 ⌊n⌋⌊n​⌋，下一层重新计算：

segment_size=⌊⌊n⌋⌋segment_size=⌊⌊n​⌋​⌋

也就是说，子问题规模是**逐层动态缩小**的，不是固定为 ⌊n⌋⌊n​⌋。

## 4.3 例子：n=16 n=16

- 第一层：k=⌊16⌋=4 k=⌊16​⌋=4，分成 4 段，每段大小 4；
    
- 第二层：每段长度 4，k=⌊4⌋=2 k=⌊4​⌋=2，每段再分成 2 段，大小 2；
    
- 第三层：每段长度 2，k=⌊2⌋=1 k=⌊2​⌋=1，基线返回。
    

实际子问题总数远大于 ⌊16⌋=4⌊16​⌋=4。

## 4.4 结论

- 原代码**第一层**分解成了 ⌊n⌋⌊n​⌋ 个子问题；
    
- 但递归下去后，子问题规模按 ⋅⋅​ 逐层缩小；
    
- 所以严格说，它并不是“固定分解成 ⌊n⌋⌊n​⌋ 个规模相同的子问题”，而是**动态分段递归**。
    

如果题目严格要求“分解成 ⌊n⌋⌊n​⌋ 个规模相同的子问题”，就需要**固定初始分段大小**，递归时传递同一个 `segment_size`，而不是每层重新计算。

---

# 五、为什么合并不能像标准归并那样一句 `MERGE(A,p,q,r)`？

## 5.1 标准归并为什么可以一句合并？

因为标准归并每次只分成**两个**子数组：

- 左半 A[p..q]A[p..q]；
    
- 右半 A[q+1..r]A[q+1..r]。
    

递归返回后，左右两半各自有序，只需要一次 `MERGE(A,p,q,r)` 合并两个有序数组。

## 5.2 分段归并为什么不行？

分段归并第一层分成了约 ⌊n⌋⌊n​⌋ 个有序子数组，不是 2 个，而是 nn​ 个。

例如 n=8 n=8，⌊8⌋=2⌊8​⌋=2，分成 4 段：

text

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

这时没有单一的中点 qq 可以把它们一次合并。  
`MERGE(A,p,q,r)` 只能合并**两个**有序数组，不能直接合并 4 个。

所以必须：

- 要么两两合并，多轮进行；
    
- 要么用最小堆做多路合并；
    
- 要么设计递归合并函数。
    

## 5.3 自底向上合并的原理

text

current_size = segment_size
while current_size < n
    for i = 0 to floor(n / (2*current_size))
        left = p + i * 2 * current_size
        mid = left + current_size - 1
        right = min(left + 2*current_size - 1, r)
        if mid < right
            MERGE(A, left, mid, right)
    current_size = current_size * 2

- 初始每个有序段大小为 `segment_size`；
    
- 第一轮：相邻两个 `segment_size` 段合并，得到大小 `2*segment_size` 的有序段；
    
- 第二轮：相邻两个 `2*segment_size` 段合并，得到大小 `4*segment_size`；
    
- 依次翻倍，直到整个数组有序。
    

这就是**自底向上归并**。

## 5.4 例子：n=8 n=8，k=2 k=2

分段：

text

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

递归排序每段：

text

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

第一轮 `current_size=2`：

- 合并 `[3,5]` 和 `[6,8]` → `[3,5,6,8]`
    
- 合并 `[2,7]` 和 `[1,4]` → `[1,2,4,7]`
    

第二轮 `current_size=4`：

- 合并 `[3,5,6,8]` 和 `[1,2,4,7]` → `[1,2,3,4,5,6,7,8]`
    

---

# 六、能不能改成“隐式递归合并”？

可以。思路是把“自底向上循环”改成“递归合并相邻子数组”。

## 6.1 递归合并版本

text

MERGE-SORT-SQRT-RECURSIVE(A, p, r)
    n = r - p + 1
    if n <= 1
        return
    segment_size = floor(sqrt(n))
    if segment_size < 1
        segment_size = 1
    num_segments = floor(n / segment_size)
    if n % segment_size != 0
        num_segments += 1
    for i = 0 to num_segments - 1
        start = p + i * segment_size
        end = min(p + (i+1)*segment_size - 1, r)
        MERGE-SORT-SQRT-RECURSIVE(A, start, end)
    if num_segments > 1
        MERGE-SQRT-SUBARRAYS(A, p, r, segment_size, num_segments)

text

MERGE-SQRT-SUBARRAYS(A, p, r, segment_size, num_segments)
    if num_segments <= 1
        return
    for i = 0 to floor(num_segments / 2) - 1
        left = p + i * 2 * segment_size
        mid = left + segment_size - 1
        right = min(left + 2*segment_size - 1, r)
        if mid < right
            MERGE(A, left, mid, right)
    new_segment_size = segment_size * 2
    new_num_segments = ceil(num_segments / 2)
    MERGE-SQRT-SUBARRAYS(A, p, r, new_segment_size, new_num_segments)

## 6.2 与原来自底向上循环的区别

|特性|自底向上循环|递归合并|
|---|---|---|
|合并逻辑| `while current_size < n` | `MERGE-SQRT-SUBARRAYS` 递归|
|代码风格|迭代|递归|
|与标准归并相似性|较低|较高|
|本质|多轮两两合并|多轮两两合并|
|复杂度|O(nlog⁡n)O(nlogn)|O(nlog⁡n)O(nlogn)|

两者本质相同，只是把循环写成了递归。

---

# 七、分段归并与标准二路归并的核心区别

|维度|标准二分归并|分段归并（nn​）|
|---|---|---|
|分解方式|严格二分|分成 ⌊n⌋⌊n​⌋ 段|
|子问题规模|n/2 n/2|约 nn​|
|子问题数量|每层固定 2 个|每层约 nn​ 个|
|递归深度|O(log⁡n)O(logn)|O(log⁡log⁡n)O(loglogn)（若每层开平方）|
|合并方式|一次 `MERGE(A,p,q,r)` |多轮两两合并 / 多路堆合并|
|合并次数|每层 1 次|每层多次|
|递归式|T(n)=2 T(n/2)+Θ(n)T(n)=2 T(n/2)+Θ(n)|T(n)=Θ(n)T(n)+Θ(nlog⁡n)T(n)=Θ(n​)T(n​)+Θ(nlogn)|
|总复杂度|Θ(nlog⁡n)Θ(nlogn)|O(nlog⁡n)O(nlogn)|
|实现难度|简单|较复杂|
|实际效率|通常更高|常数更大，但缓存局部性可能更好|

---

# 八、分治三步在分段归并中的对应

|步骤|标准二分归并|分段归并|
|---|---|---|
|分解 Divide| `q = floor((p+r)/2)` | `segment_size = floor(sqrt(n))`，分段|
|解决 Conquer|递归左右两半|递归每个子段|
|合并 Combine| `MERGE(A,p,q,r)` |自底向上多轮 `MERGE`，或递归 `MERGE-SQRT-SUBARRAYS` |

核心思想一致，但：

- 标准归并的“合并”是**一次两个**；
    
- 分段归并的“合并”是**多个有序段逐轮合并**。
    

---

# 九、复杂度分析

## 9.1 标准归并

T(n)=2 T(n/2)+Θ(n)=Θ(nlog⁡n)T(n)=2 T(n/2)+Θ(n)=Θ(nlogn)

## 9.2 分段归并（分块排序 + 合并）

设 k=⌊n⌋k=⌊n​⌋，子数组个数 m=Θ(n)m=Θ(n​)。

分块排序：

m⋅O(klog⁡k)=Θ(n)⋅O(nlog⁡n)=O(nlog⁡n)=O(nlog⁡n)m⋅O(klogk)=Θ(n​)⋅O(n​logn​)=O(nlogn​)=O(nlogn)

合并：

- 两两合并：log⁡2(n)=12 log⁡2 nlog 2​(n​)=21​log 2​n 轮，每轮 O(n)O(n)，总 O(nlog⁡n)O(nlogn)；
    
- 堆多路合并：O(nlog⁡m)=O(nlog⁡n)=O(nlog⁡n)O(nlogm)=O(nlogn​)=O(nlogn)。
    

总复杂度：

O(nlog⁡n)+O(nlog⁡n)=O(nlog⁡n)O(nlogn)+O(nlogn)=O(nlogn)

所以：

T(n)=O(nlog⁡n)T(n)=O(nlogn)​

---

# 十、最终结论

1. **标准归并排序**是二分递归，递归式：
    

T(n)=2 T(n/2)+Θ(n)=Θ(nlog⁡n)T(n)=2 T(n/2)+Θ(n)=Θ(nlogn)

2. **题目要求的分段归并排序**是把数组分成 ⌊n⌋⌊n​⌋ 段，每段大小约 ⌊n⌋⌊n​⌋，递归排序后再合并。
    
3. **第一层确实分成了约 ⌊n⌋⌊n​⌋ 个子问题**，但递归下去后子问题规模会动态缩小，不是固定规模。
    
4. **合并不能像标准归并那样一句 `MERGE(A,p,q,r)` **，因为第一层有多个有序段，不是两个。必须：
    
    - 自底向上两两合并；
        
    - 或用最小堆做多路合并；
        
    - 或写成递归合并函数 `MERGE-SQRT-SUBARRAYS`。
        
5. **自底向上合并和递归合并本质相同**，都是多轮两两合并，只是循环 vs 递归的写法区别。
    
6. **分段归并的总复杂度仍是 O(nlog⁡n)O(nlogn)**，但常数通常比标准二路归并大；它的潜在优势在于缓存局部性和并行化。
    
7. **分治三步始终存在**：
    
    - 分解：按 nn​ 分段；
        
    - 解决：递归排序每段；
        
    - 合并：多轮合并所有有序段。
        
8. **一句话总结**：
    

> 标准归并是“二分递归 + 一次合并两个”，分段归并是“nn​ 分段递归 + 多轮合并多个”。两者最终都是 O(nlog⁡n)O(nlogn)，但递归结构、合并方式、代码复杂度不同。



## 1.1 原代码

text

MERGE-SORT-SQRT(A, p, r)
    n = r - p + 1
    if n <= 1
        return
    segment_size = floor(sqrt(n))
    if segment_size < 1
        segment_size = 1
    // 计算实际分段数
    num_segments = floor(n / segment_size)
    if n % segment_size != 0
        num_segments = num_segments + 1
    // 递归排序每个分段
    for i = 0 to num_segments-1
        start = p + i * segment_size
        end = min(p + (i+1)*segment_size - 1, r)
        MERGE-SORT-SQRT(A, start, end)
    // 合并所有分段
    current_size = segment_size
    while current_size < n
        for i = 0 to floor(n/(2*current_size))
            left = p + i * 2 * current_size
            mid = left + current_size - 1
            right = min(left + 2*current_size - 1, r)
            if mid < right
                MERGE(A, left, mid, right)
        current_size = current_size * 2

## 1.2 结构分解

|部分|作用|
|---|---|
| `segment_size = floor(sqrt(n))` |分解：按 nn​ 分段|
| `for i = 0 to num_segments-1` |解决：递归排序每个分段|
| `while current_size < n` |合并：自底向上多轮合并|

## 1.3 迭代合并的问题

`while current_size < n` 这一段是**迭代**的：

- 初始 `current_size = segment_size`；
    
- 每轮合并相邻两个 `current_size` 大小的段；
    
- 然后 `current_size = current_size * 2`；
    
- 直到 `current_size >= n`。
    

这段逻辑**正确**，但和标准归并排序的递归风格不一致。  
标准归并排序的合并是隐含在递归返回过程中的，而这里是显式循环。

---

# 二、递归版合并改写

## 2.1 改写后的代码

text

MERGE-SORT-SQRT(A, p, r)
    n = r - p + 1
    if n <= 1
        return
    segment_size = floor(sqrt(n))
    if segment_size < 1
        segment_size = 1
    // 计算实际分段数
    num_segments = floor(n / segment_size)
    if n % segment_size != 0
        num_segments = num_segments + 1
    // 递归排序每个分段
    for i = 0 to num_segments-1
        start = p + i * segment_size
        end = min(p + (i+1)*segment_size - 1, r)
        MERGE-SORT-SQRT(A, start, end)
    // 递归合并所有分段
    MERGE-SORT-SQRT-RECURSIVE(A, p, r, segment_size)
MERGE-SORT-SQRT-RECURSIVE(A, p, r, current_size)
    n = r - p + 1
    if current_size >= n
        return
    // 合并相邻的两个 current_size 大小的段
    for i = 0 to floor(n/(2*current_size))
        left = p + i * 2 * current_size
        mid = left + current_size - 1
        right = min(left + 2*current_size - 1, r)
        if mid < right
            MERGE(A, left, mid, right)
    // 递归处理更大的 current_size
    MERGE-SORT-SQRT-RECURSIVE(A, p, r, current_size * 2)

## 2.2 核心变化

|原版|递归版|
|---|---|
| `while current_size < n` | `if current_size >= n: return` |
| `current_size = current_size * 2` |递归调用 `current_size * 2` |
|显式循环|隐式递归|

两者**逻辑完全等价**，只是把循环变量 `current_size` 变成了递归参数。

---

# 三、为什么递归版等价于原迭代版

## 3.1 迭代版执行过程

以 n=8 n=8，`segment_size=2` 为例：

text

current_size = 2
    合并 [0..1] 和 [2..3] → [0..3]
    合并 [4..5] 和 [6..7] → [4..7]
current_size = 4
    合并 [0..3] 和 [4..7] → [0..7]
current_size = 8
    退出循环

## 3.2 递归版执行过程

text

MERGE-SORT-SQRT-RECURSIVE(A, 0, 7, 2)
    current_size = 2 < 8
    合并 [0..1] 和 [2..3] → [0..3]
    合并 [4..5] 和 [6..7] → [4..7]
    递归调用 MERGE-SORT-SQRT-RECURSIVE(A, 0, 7, 4)
MERGE-SORT-SQRT-RECURSIVE(A, 0, 7, 4)
    current_size = 4 < 8
    合并 [0..3] 和 [4..7] → [0..7]
    递归调用 MERGE-SORT-SQRT-RECURSIVE(A, 0, 7, 8)
MERGE-SORT-SQRT-RECURSIVE(A, 0, 7, 8)
    current_size = 8 >= 8
    return

完全等价。

## 3.3 终止条件

text

if current_size >= n
    return

对应原迭代版的：

text

while current_size < n

当 `current_size >= n` 时，说明所有段已经合并成一个整体，递归结束。

---

# 四、与标准归并排序递归结构的对比

## 4.1 标准归并排序

text

MERGE-SORT(A, p, r)
    if p >= r
        return
    q = floor((p + r) / 2)
    MERGE-SORT(A, p, q)
    MERGE-SORT(A, q + 1, r)
    MERGE(A, p, q, r)

特点：

- **一次分解成两个子问题**；
    
- 递归返回时**一次合并两个**有序数组；
    
- 合并隐含在递归返回过程中。
    

## 4.2 分段归并排序（递归合并版）

text

MERGE-SORT-SQRT(A, p, r)
    ...
    for i = 0 to num_segments-1
        MERGE-SORT-SQRT(A, start, end)
    MERGE-SORT-SQRT-RECURSIVE(A, p, r, segment_size)

特点：

- **一次分解成约 nn​ 个子问题**；
    
- 递归返回后**需要多轮合并**；
    
- 合并通过 `MERGE-SORT-SQRT-RECURSIVE` 递归完成。
    

## 4.3 对比表

|维度|标准归并|分段归并（递归合并）|
|---|---|---|
|分解方式|二分|nn​ 分段|
|子问题数|2|约 nn​|
|合并函数| `MERGE(A,p,q,r)` | `MERGE-SORT-SQRT-RECURSIVE` |
|合并轮数|1|log⁡2(n)log 2​(n​) 轮|
|合并方式|一次两个|每轮多个两两合并|
|递归深度|O(log⁡n)O(logn)|O(log⁡log⁡n)O(loglogn) + 合并递归|
|总复杂度|Θ(nlog⁡n)Θ(nlogn)|O(nlog⁡n)O(nlogn)|

---

# 五、分治三步的对应关系

## 5.1 标准归并

|步骤|代码|
|---|---|
|分解| `q = floor((p+r)/2)` |
|解决| `MERGE-SORT(A,p,q)`、`MERGE-SORT(A,q+1,r)` |
|合并| `MERGE(A,p,q,r)` |

## 5.2 分段归并（递归合并版）

|步骤|代码|
|---|---|
|分解| `segment_size = floor(sqrt(n))` |
|解决| `for i: MERGE-SORT-SQRT(A,start,end)` |
|合并| `MERGE-SORT-SQRT-RECURSIVE(A,p,r,segment_size)` |

核心区别：

- 标准归并的“合并”是**一次两个**；
    
- 分段归并的“合并”是**多轮多个**。
    

---

# 六、复杂度分析

## 6.1 分段排序阶段

设 k=⌊n⌋k=⌊n​⌋，子数组个数 m=Θ(n)m=Θ(n​)。

每个子数组大小 kk，排序代价：

O(klog⁡k)=O(nlog⁡n)O(klogk)=O(n​logn​)

所有子数组排序：

m⋅O(klog⁡k)=Θ(n)⋅O(nlog⁡n)=O(nlog⁡n)=O(nlog⁡n)m⋅O(klogk)=Θ(n​)⋅O(n​logn​)=O(nlogn​)=O(nlogn)

## 6.2 递归合并阶段

`MERGE-SORT-SQRT-RECURSIVE` 的递归深度：

- 初始 `current_size = segment_size = \sqrt n`；
    
- 每次递归 `current_size = current_size * 2`；
    
- 直到 `current_size >= n`。
    

递归次数：

log⁡2(nn)=log⁡2(n)=12 log⁡2 nlog 2​(n​n​)=log 2​(n​)=21​log 2​n

每轮合并总代价 O(n)O(n)，所以合并阶段总代价：

O(n)⋅O(log⁡n)=O(nlog⁡n)O(n)⋅O(logn)=O(nlogn)

## 6.3 总复杂度

O(nlog⁡n)+O(nlog⁡n)=O(nlog⁡n)O(nlogn)+O(nlogn)=O(nlogn)

即：

T(n)=O(nlog⁡n)T(n)=O(nlogn)​

与标准归并排序相同。

---

# 七、完整伪代码

text

MERGE-SORT-SQRT(A, p, r)
    n = r - p + 1
    if n <= 1
        return
    segment_size = floor(sqrt(n))
    if segment_size < 1
        segment_size = 1
    num_segments = floor(n / segment_size)
    if n % segment_size != 0
        num_segments = num_segments + 1
    for i = 0 to num_segments - 1
        start = p + i * segment_size
        end = min(p + (i+1)*segment_size - 1, r)
        MERGE-SORT-SQRT(A, start, end)
    MERGE-SORT-SQRT-RECURSIVE(A, p, r, segment_size)
MERGE-SORT-SQRT-RECURSIVE(A, p, r, current_size)
    n = r - p + 1
    if current_size >= n
        return
    for i = 0 to floor(n / (2*current_size))
        left = p + i * 2 * current_size
        mid = left + current_size - 1
        right = min(left + 2*current_size - 1, r)
        if mid < right
            MERGE(A, left, mid, right)
    MERGE-SORT-SQRT-RECURSIVE(A, p, r, current_size * 2)

---

# 八、Python 实现

python

import math
def merge(A, p, q, r):
    nL = q - p + 1
    nR = r - q
    L = A[p:q+1]
    R = A[q+1:r+1]
    i = j = 0
    k = p
    while i < nL and j < nR:
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1
    while i < nL:
        A[k] = L[i]
        i += 1
        k += 1
    while j < nR:
        A[k] = R[j]
        j += 1
        k += 1
def merge_sort_sqrt_recursive(A, p, r, current_size):
    n = r - p + 1
    if current_size >= n:
        return
    i = 0
    while i <= n // (2 * current_size):
        left = p + i * 2 * current_size
        mid = left + current_size - 1
        right = min(left + 2 * current_size - 1, r)
        if mid < right:
            merge(A, left, mid, right)
        i += 1
    merge_sort_sqrt_recursive(A, p, r, current_size * 2)
def merge_sort_sqrt(A, p, r):
    n = r - p + 1
    if n <= 1:
        return
    segment_size = int(math.floor(math.sqrt(n)))
    if segment_size < 1:
        segment_size = 1
    num_segments = n // segment_size
    if n % segment_size != 0:
        num_segments += 1
    for i in range(num_segments):
        start = p + i * segment_size
        end = min(p + (i + 1) * segment_size - 1, r)
        merge_sort_sqrt(A, start, end)
    merge_sort_sqrt_recursive(A, p, r, segment_size)
if __name__ == "__main__":
    A = [5, 3, 8, 6, 2, 7, 1, 4]
    merge_sort_sqrt(A, 0, len(A) - 1)
    print(A)

输出：

text

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

---

# 九、最终总结

1. **原版合并是迭代的**：`while current_size < n` 循环，逐轮扩大合并范围。
    
2. **递归版合并**：把循环改成递归函数 `MERGE-SORT-SQRT-RECURSIVE(A,p,r,current_size)`。
    
3. **两者完全等价**：`current_size` 每次翻倍，直到 `current_size >= n` 终止。
    
4. **与标准归并的区别**：
    
    - 标准归并：一次二分，一次合并两个；
        
    - 分段归并：一次分成 nn​ 段，多轮合并多个。
        
5. **分治三步仍然成立**：
    
    - 分解：按 nn​ 分段；
        
    - 解决：递归排序每段；
        
    - 合并：递归多轮两两合并。
        
6. **总复杂度**：
    

T(n)=O(nlog⁡n)T(n)=O(nlogn)​

7. **一句话**：
    

> 把 `while current_size < n` 改成 `if current_size >= n: return` + 递归调用 `current_size * 2`，就完成了从迭代合并到递归合并的改写；逻辑不变，复杂度不变，只是代码风格更贴近标准归并排序的递归形式。