双向合并排序和合并排序

Question

双向合并排序与合并排序有何区别？

假设合并排序中有5个数字要排序：{8,9,1} {6,4}

Step2：{8,9} {1} {6} {4}

Step3:{8} {9} {1} {6} {4}

现在合并

Step4：{8-9} {1} {4,6}

Step5：{1,8,9} {4,6}

Step6：{1,4,6,8,9}

但是在两种方式的合并排序中，我们将数组划分为两个元素(但根据维基百科的说法，在合并每个元素部分之前需要排序。algorithm)，所以它也从单个元素开始并合并它们，对吗？因此，数组的步骤:8,9,1,6,4

Step1:{8,9} {1,6} {4}，这是最后合并的奇数元素

Step2：{1,6,8,9}。{4}

Step3：{1,4,6,8,9}

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

Answer 1

双向合并排序合并排序比合并排序更有效吗？

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

通常，优化的自下而上合并排序比优化的自上而下合并排序略高一些。自顶向下的合并排序对数组的递归“拆分”生成的索引执行O(n)堆栈操作。如果n不是2的幂，那么自下而上的合并排序会进行更多的比较和移动，但它比自顶向下的合并排序的堆栈操作开销小。对于大数组，差异小于5%。

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

自顶向下的合并排序主要是为了学习。尽管性能和堆栈空间差异很小，但大多数库都使用一些自下而上的合并排序来实现稳定的排序。