并行Merge Sort算法加速比疑问：最大有效核心数为何是log₂(n)而非n/2？

问题拆解 #

你原本认为归并排序树最底层有n/2个并行任务，所以最大有效核心数是n/2，但参考答案指出无需重构算法的情况下，最大有效核心数是log₂n。核心矛盾在于你混淆了单一层级的峰值并行任务数和整个算法流程中能持续利用的核心数上限。

为什么n/2不是有效上限？ #

归并排序的执行是分层串行推进的：

• 分治阶段：从整个数组开始，逐层拆分直到单个元素，每层的并行任务数从1增长到n/2；
• 合并阶段：从单个元素开始，逐层合并直到整个数组，每层的并行任务数从n/2缩减到1。

但问题在于，n/2个并行任务只在最底层的那一步出现，其余绝大多数时间里，并行任务数远小于n/2。比如n=8，最底层有4个并行任务，但上层只有2个、1个任务——如果你用8个核心，那在执行上层任务时，大部分核心都处于空闲状态，全流程下来核心的平均利用率极低。

为什么log₂n是最大有效核心数？ #

归并排序的关键路径长度是log₂n（从根到叶子的层数），这意味着整个排序过程至少需要log₂n个“串行步骤”——每一层的任务必须等上一层全部完成才能启动。

从加速比的实际收益来看：

• 当核心数≤log₂n时，每一层的并行任务都能被核心充分覆盖，加速比会随着核心数增加而明显提升；
• 当核心数超过log₂n后，只有最底层的任务能用到更多核心，但这一步的时间占总时间的比例仅为1/log₂n（总时间是O(nlogn)，最底层合并时间是O(n)），再多的核心也无法大幅缩短总耗时，加速比的提升几乎可以忽略。

更关键的是，原递归并行的归并排序算法（给左右子树各开线程的方式）本身的并行粒度就是按层划分的，无法将合并操作拆分成更细的并行任务来利用更多核心——如果要让n/2个核心全程工作，你需要重构算法（比如流水线合并、分块合并等），这已经超出了“无需重构算法”的前提。

举个具体例子 #

假设n=1024（log₂n=10）：

• 用10个核心：每一层的并行任务数（1、2、4、8、16…512）中，前4层（1-8个任务）能被10个核心完全覆盖，后6层（16-512个任务）需要排队执行，但核心的整体利用率已经很高，总耗时接近理论下限；
• 用512个核心：只有最后两层（256、512个任务）能占满核心，前8层（1-128个任务）最多只用128个核心，剩下的384个核心全程闲置，总耗时仅比用10个核心快一点点，但核心利用率极低。

所以从“有效利用核心、获得显著加速比”的角度，log₂n是无需重构算法的最大核心数。

内容的提问来源于stack exchange，提问作者tiredStudent