使用 N 路合并的时间复杂度

我正在研究 2 路合并排序算法，并思考是否通过减少合并次数我们可以在时间方面获得更好的收益。

例如，在 2 路合并中，我们有以下递归：

T(n) = 2T(n/2) + O(n)

时间复杂度为 N.log-base 2(N)

如果我将问题除以 4 并合并 4 个子数组，我会得到

T(n) = 4T(n/4) + O(n)

时间复杂度应该为 N.log-base4(N)

既然合并传递的数量减少了，那么在实现合并排序时是否应该考虑这一点？

例如，对于 64 个元素的数组，第一种方法将有 6 次传递，而使用第二种方法将有 3 次传递。

Edit:

好的，那么对于 2T(n/2)，我们每次传递进行 N 次比较，而对于 4T(n/4)，我们最终每次传递进行 3*N 次比较？移动元素以产生排列的成本如何，每次传递时都保持不变吗？

请注意，数字的以 4 为底的对数恰好是数字以 2 为底的对数的一半；因此，您只是引入了常数因子加速。除非你不是，因为你在实际合并的成本中引入了类似的常数因子减慢（2 路合并需要每个项目 1 次比较，4 路可能需要最多 3 次）。因此，虽然通行证的数量可能会减少，但每一次通行证的成本都会更高。因此，您已经使代码变得相当复杂，并且其好处也受到质疑。