我正在研究 2 路合并排序算法，并在思考是否通过减少合并通道可以在时间方面获得更好的收益。
例如，在 2 路合并中，我们有以下重复：
T(n) = 2T(n/2) + O(n)
这具有 N.log-base2(N) 的时间复杂度
如果我将问题除以 4 并合并 4 个子数组，我将得到
T(n) = 4T(n/4) + O(n)
这应该具有 N.log-base4(N) 的时间复杂度
由于合并通道的数量减少了，在实现合并排序时是否应该考虑这一点？
例如，对于 64 个元素的数组，第一种方法将有 6 次通过，而使用第二种方法将有 3 次通过。
编辑：
好的，所以使用 2T(n/2) 我们每次通过进行 N 次比较，而使用 4T(n/4) 我们最终每次通过进行 3*N 比较？将元素移动到结果数组的成本如何，每次通过时都保持不变吗？
请注意，数字的以 4 为底的对数恰好是数字的以 2 为底的对数的一半；因此，您只是引入了恒定因子加速。除非你不是，因为你在实际合并的成本中引入了一个类似的常数因子 SLOWDOWN（2 路合并需要每个项目 1 次比较，4 路可能需要多达 3 次）。因此，尽管通行证可能较少，但通行证的成本更高。所以你已经把代码复杂化了一点，好处是有问题的。
这听起来很合理，但实际上并非如此，因为在这种情况下，您必须至少进行 5 次比较才能对每 4 个元素进行排序。这样你就有 5*N*log4(N) 比较，这比 N*log2(N) 大 5*log(2)/log(4)
分解树的高度是 log 4 n，但运行时间不是 n log 4 n。
在第一步中，您有四个大小为 n/4 的列表，它们的合并需要 n/4 + n/4 + n/2 比较。但在正常情况下，它需要 n/2 比较，所以你是树高度的一半，但是你将每个合并乘以两个，所以总运行时间并不比除以 2 部分好。（您可以证明对于树的其他深度，与具有两个分支的树相比，您应该至少进行两次比较）。
PS：运行时间是指比较次数。