两段有序数组归并成一段，顺序算法每次比较两端最小值，耗线性时间。要让多个处理器同时工作，不能简单地把两段输入各切成相同长度：某一段的全部元素可能都应排在另一段之前，输入位置并不对应输出位置。

本篇用co-ranking把输出区间映射成输入区间，再并行归并。证明使用共享数组模型；Python实验使用独立进程，父进程的切片、传输和结果拼接另行计入实际时间。

输入顺序与相等键

输入A、B是两个非递减整数数组，长度分别为m、n，总长N=m+n。输出包含所有元素且非递减，不修改输入。相等键约定A中的元素先于B，同一数组内部保持原顺序。

空数组与重复值合法。serial_merge与parallel_merge检查元素为整数且已排序；parallel_merge还拒绝整数分区数P≤0。co_rank只检查前缀长度r范围，它以两输入已排序为前提，不单独扫描验证排序。接口不提供任意比较器、浮点NaN或外部文本解析。

按输出位置把[0,N)分成P段，边界r_j=⌊jN/P⌋。每段长度相差至多1；P>N时会出现空段，不能假设每个任务都有工作。

一个输出前缀来自多少输入

对前r个输出元素，设其中i个来自A，j个来自B，则i+j=r。合并边界应满足：

A[i−1]≤B[j],B[j−1]<A[i].A[i-1]\le B[j],\qquad B[j-1]<A[i].

涉及i=0、i=m、j=0、j=n时，跳过不存在元素对应的比较。第一个非严格不等式允许A的相等元素留在前缀内，第二个严格不等式阻止B的相等元素排到仍未取出的A元素之前。这一对条件固定了稳定归并的唯一前缀划分。

合法i范围为max(0,r−n)到min(r,m)。若A[i−1]>B[j]，取了太多A元素，应减小i；若B[j−1]≥A[i]，取了太少A元素，应增大i。沿这个方向二分就能找到边界，单次最坏O(1+log(min(m,n)+1))次比较。

第一个不等式比较前缀A最大值与后缀B最小值，第二个比较前缀B最大值与后缀A最小值。结合两个输入内部已排序，前缀确实包含全局前r个元素，而且相等键次序符合约定。

不相交输出段为何可以独立归并

对相邻输出边界r_j与r_{j+1}分别求co-rank，得到(i_j,j_j)与(i_{j+1},j_{j+1})。第j个任务只归并A[i_j:i_{j+1}]和B[j_j:j_{j+1}]，写入自己的输出区间。

每个边界对应同一稳定全序的前缀，所以输入切片连续、互不重复，所有任务合起来覆盖两份输入。单个任务用普通稳定归并即可；输出区间按序连接后，也没有跨段逆序或遗漏。

这里消除写冲突靠的是输出区间不相交，不需要多个任务用原子自增争抢一个输出下标。若换成共享计数器，原子操作与竞争就成为额外成本，不能自动纳入这个分区算法的界。

work、span与给定P的时间

固定计算依赖图的总工作量记为W，最长依赖路径长度记为S，也称span。理想P处理器至少需要max(W/P,S)时间：既要完成全部工作，也不能越过依赖链。对就绪任务不闲置处理器的贪心调度，有T_P≤W/P+S的上界。

这些结论要求每个操作成本和依赖已包含在图里，不允许事后把序列化、内存访问或同步当作免费的操作。W与S是同一个算法的两个量，也不能把一段串行实现的工作量与另一算法的跨度拼起来。

论文中，各处理器独立求自己区间的两个co-rank，再在线性大小的切片上归并。允许并发读、独占输出写的CREW PRAM模型下，每处理器时间为O(N/P+1+log(min(m,n)+1))，总工作为O(N+P(1+log(min(m,n)+1)))。

当分区开销不超过线性归并工作时，这个方法才具有工作最优性。给定P的分区算法时间不是对同一固定DAG无限增加处理器得到的跨度；讨论span时必须先固定任务划分。

以上均是确定性的最坏操作界，不是期望或高概率界。机器字能容纳数组索引与整数比较是模型前提，大整数比较或内存层级成本需另计。

Python进程版多支付了什么

本实现父进程依次求边界、复制输入切片，子进程接收任务后归并，父进程按区间顺序拼接结果。切片和拼接复制O(N)个元素，还要创建并遍历P份任务与结果，共O(N+P)工作；边界计算在父进程串行执行。即使子任务足够快，这条串行路径也没有消失。

ProcessPoolExecutor的任务与结果需要可pickle，工作函数放在模块顶层，入口使用main guard。实验显式采用spawn启动方式，不依赖不同Python版本或平台的默认值。max_workers=P是进程池上限，不表示绑定了P个物理核，也不证明所有进程都同时执行。

归并本身不写共享输出数组，进程间传递的是Python对象。峰值空间可能同时含原数组、切片、序列化缓冲和返回列表；没有测量这些占用时，不把PRAM输出数组的空间直接当作进程内存。

实际运行

仓库根目录运行：

1
python3 examples/advanced-algorithms/check_parallel_merge.py

本次Python 3.14.4、macOS arm64、spawn执行退出码为0。穷举1225个有序数组对，对8575个输出前缀使用带来源与原位置标记的独立排序参照，核对co-rank中的A元素数量。仅检查重复整数的最终数值相等看不出稳定性，所以没有用它代替来源核对。另有5种拒绝检查、3个实际进程边界实例，包括空输入与P>N。

基准的两数组各100000项，固定种子20260920、数值范围0到9999，包含重复键；精确参照为sorted(A+B)。所有方法使用相同输入，各预热一次，再交替执行顺序运行三轮。计时含排序输入验证、分区、切片、全新进程池、序列化、归并、拼接及关闭池，不含生成输入和结果比对。

配置 三轮时间ms 中位时间ms 串行/本配置 每轮参与工作进程数
serial 24.713, 20.279, 23.508 23.508 1.000 主进程
1 120.786, 122.792, 120.674 120.786 0.195 1, 1, 1
2 142.315, 201.738, 213.802 201.738 0.117 2, 2, 2
4 122.514, 127.011, 133.217 127.011 0.185 3, 3, 3

表中P配置是max_workers上限；P=4各轮实际执行任务的进程只有3个。系统报告14个逻辑CPU，实验没有设置亲和性或测量同时占用核数，因此不能把P=4这行称为四个物理处理器的吞吐结果。

三种进程池配置在这次端到端实验中均慢于串行。加速比分母是相应配置的中位时间，分子统一使用主进程串行归并的中位时间，没有用进程池P=1时间替换基线。三轮结果不足以给出稳定置信区间；完整纳秒计时、参与PID、源码与结果SHA及环境记录见writing-plans/advanced-algorithms/evidence/parallel-merge-results.json。

加速比低于1只表明这组配置比选定串行基线慢，不能单凭这个结果断定内存带宽已经饱和。进程启动、对象复制、调度和内存竞争都可能影响结果；本实验没有采集带宽或硬件计数器。

练习

  1. A=[1,1]、B=[1,2]，分别求r=0到4的co-rank。若把第二个严格不等式改为非严格，会怎样破坏A优先的唯一划分？
  2. 把P增大到N以上，归并任务长度与边界计算数量分别怎样变化？解释为什么理想时间公式中的分区项和实际进程启动成本都不能省略。

参考资料