CS267 · 第 23 课

选择与排序

从递归式的 Master Method 出发，深入探讨并行选择问题（Median of Medians）、并行归并排序以及分布式内存上的 Sample Sort，理解 Work-Span 模型下的复杂度分析。

---

课程大纲

• Master Method（主方法）——求解分治递归式的万能工具
• 选择问题（Selection Problem）——找第 k 小元素
• Median of Medians 算法——最坏情况线性时间选择
• 并行选择——Weighted Median of the Medians
• 归并排序（MergeSort）——串行与并行实现
• 并行归并（Parallel Merge）——P_Merge 算法
• 桶排序与 Sample Sort——分布式排序
• 大规模 Sample Sort 的挑战

---

Master Method（主方法）

Master Method 是求解形如 T(n) = aT(n/b) + f(n) 递归式的系统方法，其中 a ≥ 1、b > 1，且 f(n) 渐近为正。这个框架在分析分治算法时无处不在。

情况 1：叶节点主导

若 f(n) = O(n^log_ba-ε) 对某个常数 ε > 0 成立，则递归树的工作量主要集中在叶节点层，解为：

T(n) = Θ(n^(log_b a))

这意味着合并开销比叶节点工作量增长得更快，叶节点决定了总体复杂度。

情况 2：均衡情况

若 f(n) = Θ(n^log_ba lg^kn) 对某个常数 k ≥ 0 成立，则每一层的工作量大致相等，解为：

T(n) = Θ(n^(log_b a) lg^(k+1) n)

经典例子：归并排序中 a = 2, b = 2, k = 0，故 T(n) = Θ(n lg n)。

情况 3：根节点主导

若 f(n) = Ω(n^log_ba+ε) 对某个常数 ε > 0 成立，且满足正则条件 a·f(n/b) ≤ c·f(n)（其中 c < 1），则：

T(n) = Θ(f(n))

正则条件保证了递归过程中工作量几何级数衰减，根节点的开销主导整个过程。

情况	条件	解	直觉
Case 1	f(n) = O(nlogba-ε)	Θ(nlogba)	叶节点主导
Case 2	f(n) = Θ(nlogba lgkn)	Θ(nlogba lgk+1n)	各层均衡
Case 3	f(n) = Ω(nlogba+ε) + 正则条件	Θ(f(n))	根节点主导

---

选择问题（Selection Problem）

选择问题是指：在包含 N 个元素的列表中找到第 k 小的元素。这是一个基础构建块，在统计学（中位数、四分位数）、图算法（MCL 聚类）和负载均衡中频繁出现。

Quickselect 算法

由 Tony Hoare 设计，类似于快速排序，但只向一侧递归。选择一个 pivot 后将数组分为"小于 pivot"和"大于 pivot"两部分，然后只在包含第 k 元素的那一侧继续递归。

• 平均时间：O(N)
• 最坏时间：O(N²)（当 pivot 选择极度不平衡时）

---

Median of Medians 算法（串行）

Median of Medians 的核心思想是精心选择 pivot，保证每次递归都能丢弃一定比例的元素，从而保证线性时间复杂度。

算法步骤

1. 将列表划分为约 N/5 个子列表，每个子列表至少 5 个元素
2. 对每个子列表排序并找出中位数，得到"中位数列表" M
3. 递归地在 M 上调用 SELECT，找到"中位数的中位数" mm
4. 使用 mm 作为 pivot 对整个列表进行划分，得到三个集合 A（小于）、B（等于）、C（大于）
5. 根据 k 落入哪个集合，要么返回 mm，要么在 A 或 C 上递归

// SELECT(S, k): 在集合 S 中找第 k 小元素
SELECT(S, k) {
    M = DIVIDE_AND_SORT(S, 5);   // O(N)，将 S 分为 N/5 组并排序
    mm = SELECT(M, |M|/2);       // 递归找中位数的中位数，T(N/5)
    [A, B, C] = PARTITION(S, mm); // O(N)，按 mm 划分

    if (k > |A| && k <= |A| + |B|)
        return mm;                // mm 就是答案
    else if (k <= |A|)
        return SELECT(A, k);      // 在较小的一半递归
    else
        return SELECT(C, k - |A| - |B|); // 在较大的一半递归
}

为什么是 7N/10？

关键在于确定递归调用时集合大小的上界。设 A' 是 M 中所有小于 mm 的中位数对应的完整组，C' 是大于 mm 的那些：

• |A'| ≥ 3N/10：每组 5 个中至少有 3 个小于其对应中位数，而这些中位数又小于 mm
• |C'| ≥ 3N/10：对称地，至少有 3N/10 个元素大于 mm

因此，无论递归进入 A 还是 C，最多只有 N - 3N/10 = 7N/10 个元素。

复杂度分析

递归式为：

T(n) ≤ T(n/5) + T(7n/10) + O(n)

展开递归树：每层工作量以 9/10 的比率递减：

T(n) = c(n + 9n/10 + 81n/100 + ...)
     = cn · (1 + 9/10 + (9/10)² + ...)
     = cn · 1/(1 - 9/10)
     = O(n)

---

并行选择（Parallel Selection）

在分布式内存系统中，每个处理器持有一部分数据。朴素的并行 Median of Medians 存在负载不均衡问题：随着递归深入，数据分布变得不均匀，需要频繁的数据重分布和通信。

Weighted Median of the Medians 算法

核心洞察：与其费力处理负载不均衡，不如直接忽略它！

给定 p 个不同元素 m₁, m₂, ..., mₚ 及其对应正权重 w₁, w₂, ..., wₚ（满足 Σwᵢ = 1），加权中位数 M 满足：

Σ_{mᵢ < M} wᵢ ≤ 1/2  且  Σ_{mᵢ > M} wᵢ ≤ 1/2

// 并行选择：在分布式内存中找第 k 小元素
PARALLEL_SELECT(S, k) {
    lm = SELECT(S, |S|/2);          // 每个处理器找本地中位数
    LMS = MPI_Allgather(lm);         // 交换所有本地中位数
    wmm = WeightedMedian(LMS);       // 计算加权中位数（冗余计算）

    [A, B, C] = PARTITION(S, wmm);   // 本地划分
    ls = MPI_Allreduce(|A|, SUM);    // 全局小于 wmm 的元素数
    eq = MPI_Allreduce(|B|, SUM);    // 全局等于 wmm 的元素数

    if (k > ls && k <= ls + eq)
        return wmm;
    else if (k <= ls)
        return PARALLEL_SELECT(A, k);        // 递归，最多 3N/4
    else
        return PARALLEL_SELECT(C, k - ls - eq); // 递归，最多 3N/4
}

为什么是 3N/4？

根据加权中位数定义，权重和 ≤ 1/2 意味着至少一半的元素在 M 的"两侧"。将权重替换为各处理器的元素数 nᵢ：

• 对处理器 i，小于等于本地中位数 mᵢ 的元素至少有 nᵢ/2 个
• 所有满足 mᵢ ≤ M 的处理器，其"下半部分"元素总数 ≥ N/4
• 同理，"上半部分"元素总数也 ≥ N/4

因此，每次递归至少丢弃 N/4 个元素，最多保留 3N/4。

复杂度分析

指标	复杂度	说明
Tcomm(n)	O(α log²p + β(p log p + n/p))	粗化基本情况：O(log p) 轮递归 + 最终本地排序
Tcomp(n)	O((n/p) · log n)	本地列表不保证收缩，最终需要本地排序
递归深度	O(log n) → 粗化后 O(log p)	每轮至少丢弃 1/4 元素

---

归并排序（MergeSort）

归并排序是基于分治范式的经典递归排序算法，其核心操作是合并（merge）：将两个已排序序列合并为一个有序序列。

串行合并操作

// 合并两个已排序数组 A[na] 和 B[nb] 到 C[]
void Merge(T *C, T *A, T *B, int na, int nb) {
    while (na > 0 && nb > 0) {
        if (*A <= *B) { *C++ = *A++; na--; }
        else          { *C++ = *B++; nb--; }
    }
    while (na > 0) { *C++ = *A++; na--; }
    while (nb > 0) { *C++ = *B++; nb--; }
}
// 时间复杂度：Θ(n)，其中 n = na + nb

并行归并排序框架

// 并行归并排序：将 A[0..n-1] 排序到 B[0..n-1]
void MergeSort(T *B, T *A, int n) {
    if (n == 1) {
        B[0] = A[0];
    } else {
        T *C = new T[n];         // 临时数组
        #pragma omp parallel
        {
            #pragma omp single
            {
                #pragma omp task
                MergeSort(C, A, n / 2);             // 排序左半
                #pragma omp task
                MergeSort(C + n/2, A + n/2, n - n/2); // 排序右半
            }
        }
        Merge(B, C, C + n/2, n/2, n - n/2);  // 串行合并
        delete[] C;
    }
}

Work-Span 分析（朴素并行版本）

指标	递归式	解	Master Method 情况
Work T₁(n)	2T₁(n/2) + Θ(n)	Θ(n lg n)	Case 2：nlog₂2 = n
Span T∞(n)	T∞(n/2) + Θ(n)	Θ(n)	Case 3：合并步骤是串行的
Parallelism	T₁ / T∞	Θ(lg n)	太弱了！

---

并行归并（Parallel Merge）

P_Merge 算法的关键洞察是：通过二分搜索在两个数组之间"交替分割"，使得每次递归至少丢弃 1/4 的元素。

算法思想

假设 na ≥ nb（A 是较大的数组），取 A 的中点 A[mₐ]，在 B 中二分搜索 A[mₐ] 的位置 m_b。那么：

• 所有 A[0..mₐ-1] 和 B[0..m_b-1] 都小于 A[mₐ]
• 总共 mₐ + m_b 个元素已确定位置
• 两个递归子问题各自不超过原问题的 3/4

// 并行合并：将 A[na] 和 B[nb] 合并到 C[]
void P_Merge(T *C, T *A, T *B, int na, int nb) {
    if (na < nb) { P_Merge(C, B, A, nb, na); return; } // 确保 na ≥ nb
    if (na == 0) return;

    int ma = na / 2;
    int mb = BinarySearch(A[ma], B, nb);  // 在 B 中找 A[ma] 的位置
    C[ma + mb] = A[ma];                    // 放置 A[ma]

    #pragma omp parallel
    {
        #pragma omp single
        {
            #pragma omp task
            P_Merge(C, A, B, ma, mb);  // 左半部分
            #pragma omp task
            P_Merge(C + ma + mb + 1, A + ma + 1, B + mb,
                    na - ma - 1, nb - mb);  // 右半部分
        }
    }
    // 隐式 taskwait
}

Span 分析

递归式为 T_∞(n) = T_∞(3n/4) + Θ(lg n)：

T_∞(n) = T_∞(3n/4) + Θ(lg n)
Case 2: n^(log_{4/3} 1) = 1, f(n) = Θ(lg n) = Θ(lg¹ n)
=> T_∞(n) = Θ(lg² n)

Work 分析（复杂但优美）

Work 的递归式为 T₁(n) = T₁(αn) + T₁((1-α)n) + Θ(lg n)，其中 1/4 ≤ α ≤ 3/4。使用代入法证明 T₁(n) = Θ(n)：

归纳假设：T₁(k) ≤ c₁k - c₂lg k，对任意 k < n 成立

T₁(n) ≤ c₁(αn) - c₂lg(αn) + c₁(1-α)n - c₂lg((1-α)n) + Θ(lg n)
     = c₁n - c₂[lg(αn) + lg((1-α)n)] + Θ(lg n)
     = c₁n - c₂[lg(α(1-α)) + 2lg n] + Θ(lg n)
     = c₁n - c₂lg n - (c₂(lg n + lg(α(1-α))) - Θ(lg n))
     ≤ c₁n - c₂lg n    （选取足够大的 c₂）

---

并行归并排序（P_MergeSort）

将 P_Merge 替换串行 Merge，得到完全并行的归并排序：

// 并行归并排序（使用并行合并）
void P_MergeSort(T *B, T *A, int n) {
    if (n == 1) {
        B[0] = A[0];
    } else {
        T C[n];
        #pragma omp parallel
        {
            #pragma omp single
            {
                #pragma omp task
                P_MergeSort(C, A, n / 2);
                #pragma omp task
                P_MergeSort(C + n/2, A + n/2, n - n/2);
            }
        }
        P_Merge(B, C, C + n/2, n/2, n - n/2);  // 并行合并！
    }
}

复杂度分析

指标	递归式	解	说明
Work T₁(n)	2T₁(n/2) + Θ(n)	Θ(n lg n)	与串行相同，Case 2
Span T∞(n)	T∞(n/2) + Θ(lg² n)	Θ(lg³ n)	Case 2：nlog₂1 = 1
Parallelism	T₁ / T∞	Θ(n / lg² n)	大幅提升！

---

桶排序（Bucket Sort）

桶排序假设输入数据在区间 [a, b] 上均匀分布。算法将区间划分为 m 个等宽的桶，每个元素放入对应桶中，各桶内局部排序后连接。若数据确实均匀分布，每个桶大约包含 n/m 个元素，总运行时间 Θ(n lg(n/m))。

并行桶排序

并行化非常直接：选择 m = p（处理器数），每个处理器负责一个值域区间。每个处理器扫描本地列表，通过 all-to-all 通信将元素发送到目标处理器，最后各处理器对收到的元素排序。

---

样本排序（Sample Sort）

Sample Sort 是 Quicksort 的自然推广：从单个 pivot 扩展到 p 个 pivot（splitters），将数据划分为 p+1 个桶，分配给 p 个处理器并行排序。

Regular Sampling 方法

为了保证负载平衡，采用规则采样（regular sampling）策略：

1. 将 n 个元素分为 p 个块，每个块 n/p 个元素，本地排序
2. 从每个排序后的块中等间距选取 p-1 个样本
3. 将 p(p-1) 个样本收集到一个处理器，排序得到 Y
4. 从 Y 中等间距选取 p-1 个 splitters：S = {s₁, s₂, ..., s_p-1}
5. 广播 splitters，每个处理器按 splitters 划分本地数据
6. All-to-all 交换后各处理器本地排序

负载平衡保证

Regular sampling 保证每个桶的元素数 < 2n/p（即最坏负载不均衡为 2 倍）。证明思路：

• 每个样本 y_i 至少大于 n/p² 个本地元素
• s_i-1 至少大于 ((i-2)p + p/2) · n/p² 个元素
• s_i 至多多于 ((p-i)p - p/2) · n/p² 个元素
• 桶 i 的元素数 ≤ n - (lb + ub) = 2n/p

复杂度分析

步骤	时间复杂度	说明
本地排序	Θ((n/p) lg(n/p))	对 n/p 个元素排序
样本收集（gather）	Θ(p²)	收集 p(p-1) 个样本
样本排序	Θ(p² lg p)	对 p(p-1) 个样本排序
选择 splitters	Θ(p)	等间距选取 p-1 个
本地二分插入	Θ(p lg(n/p))	p-1 次二分搜索
数据重分布	O(n/p)	all-to-all 通信

---

大规模 Sample Sort 的挑战

当 Sample Sort 扩展到数万核心时，样本收集阶段会遇到严重的内存问题：

内存爆炸问题

在 20,000 核心上运行 Sample Sort，每个样本至少 12 字节（4 字节值 + 8 字节全局索引）。p(p-1) 个样本共需：

20,000 × 19,999 × 12 bytes ≈ 4.8 GB per core!

这甚至还未开始排序，仅样本就已占用每核心数 GB 内存。

解决方案

• 快速方案（Hack）：使用并行选择找中位数，交换数据后，在 p/2 个处理器上递归
• Exact Splitters：将并行选择算法泛化，直接找到能均匀划分数据的 splitters（Cheng, Shah, Gilbert, Edelman）
• 潜在创新：并行化样本 Y 的合并过程，降低每处理器内存占用

---

测验

---

要点总结

延伸阅读

• Blum, Floyd, Pratt, Rivest, Tarjan. "Time bounds for selection", J. Comput. System Sci., 1973
• Shi & Schaeffer. "Parallel Sorting by Regular Sampling", J. Parallel Distrib. Comput., 1996
• Bader & JáJá. "Practical parallel algorithms for dynamic data redistribution, median finding, and selection", 1996
• Solomonik & Kalé. "Highly scalable parallel sorting", IPDPS 2010
• Sundar, Malhotra, Biros. "Hyksort: a new variant of hypercube quicksort on distributed memory architectures", 2013
• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, Chapter 9 (Medians and Order Statistics)
• Cheng, Shah, Gilbert, Edelman. "A novel parallel sorting algorithm for contemporary architectures"

---