双向合并排序和合并排序

Question

双向合并排序与递归合并排序有何不同？

假设在合并排序中有5个数字需要排序8,9,1,6,4，我们按如下步骤1进行划分：{8,9,1}{6,4}

步骤2：{8,9}{1}{6}{4}

步骤3：{8}{9}{1}{6}{4}

现在合并

步骤4：{8,9}{1}{4,6}

步骤5：{1,8,9}{4,6}

第六步：{1,4,6,8,9}

但在双向合并排序中，我们将数组分为两个元素（但根据维基百科，在合并每两个元素之前，需要对每个部分进行排序）。https://en.wikipedia.org/wiki/K-way_merge_algorithm）那么，它也从单个元素开始，并将它们合并，对吗？数组的步骤：8,9,1,6,4

步骤1：{8,9}{1,6}{4}[即奇数元素最终合并]

步骤2：{1,6,8,9}。{4}

步骤3：{1,4,6,8,9}

所以，这里减少了步数。那么它的算法是什么？双向合并排序合并排序比合并排序更有效吗？

Answer 1

2路合并排序合并排序比合并排序更有效吗？

迭代双向合并排序的另一个名称是自底向上合并排序，而递归合并排序的另一个名称是自顶向下合并排序。

通常，优化的自底向上合并排序比优化的自顶向下合并排序效率略高。自顶向下合并排序对由数组递归“拆分”生成的索引执行O（n）堆栈操作。如果n不是2的幂，则自底向上合并排序执行更多的比较和移动，但它小于自顶向下合并排序的堆栈操作开销。对于大型阵列，差异小于5%。

对于混合插入/合并排序，它对n/m组m个元素使用插入排序，自下而上的合并排序可以调整m以处理n不是2的幂。

自顶向下的合并排序主要用于学习。尽管在性能和堆栈空间方面存在微小差异，但大多数库使用一些自下而上合并排序的变体来实现稳定排序。