一、问题背景
当算法层面已无法继续优化（如排序已是 O(n log n)），如何进一步提升性能？
答案：利用多核/多机并行计算。
核心思想：对数据分片，对无依赖关系的任务并行执行。
时间复杂度不变，但实际执行时间缩短为 1/K（K 为并行度）。
二、并行排序
2.1 归并排序并行化
将 8GB 数据分为 16 个 500MB 的子集：
Mermaid · 渲染中（下方为源码）
graph TD D[8GB 数据] --> P1[500MB 分片1] D --> P2[500MB 分片2] D --> P16[500MB 分片16] P1 --> S1[线程1排序] P2 --> S2[线程2排序] P16 --> S16[线程16排序] S1 --> M[16路归并] S2 --> M S16 --> M
步骤：
- 将数据任意分片为 K 份
- K 个线程并行排序各自分片
- 对 K 个有序结果做多路归并
2.2 快排并行化
- 扫描一遍数据，确定值域范围
- 将值域均匀划分为 K 个区间
- 将数据按值分配到对应区间
- K 个线程并行排序各区间
- 拼接结果（无需归并，天然有序）
2.3 对比
| 方案 | 分片方式 | 是否需要归并 | 类似算法 |
|---|---|---|---|
| 归并并行化 | 任意切分 |