我正在阅读第三版算法简介中的多线程合并排序。但是，我对以下合并排序算法所需的处理器数量感到困惑：
MERGE-SORT(A, p, r)
1 if p < r
2 q = (p+r)/2
3 spawn MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 sync
6 MERGE(A, p, q, r)
MERGE 是标准的合并算法。现在这个算法需要多少处理器？？虽然我假设它应该是 O(N)，但是这本书声称它是 O(log n)，为什么？请注意，我没有对 MERGE 过程进行多线程处理。一个例子的解释将非常有帮助。提前致谢。
O(log n) 值不是运行算法“需要”的 CPU 数量，而是算法实现的实际“并行度”。因为 MERGE 本身不是并行化的，所以如果 O(n) 处理器，即使您拥有所有可用的处理器，您也不会获得全部好处。
也就是说，归并排序的单线程串行时间复杂度为 O(n log n)。您可以将“n”视为合并的成本，将“log n”视为在合并排序的递归调用中计算的因素，以使数组进入可以合并的阶段。当您并行化递归，但合并仍然是串行的，您保存 O(log n) 因子但 O(n) 因子保留在那里。因此，当您有足够的可用处理器时，并行度的数量级为 O(log n)，但您无法达到 O(n)。
换句话说，即使你有 O(n) 个 CPU 可用，它们中的大多数也会很快空闲，当大型 MERGE 开始发生时，工作的 CPU 越来越少。