algorithm - 2路合并排序和合并排序

Question

2路合并排序与递归合并排序有何不同？

---

假设有 5 个数字要排序 8,9,1,6,4 在 Merge Sort 中我们这样划分 Step1: {8,9,1} {6,4}

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

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

现在合并

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

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

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

但是在 2 路合并排序中，我们将数组分成 2 个元素（但根据 wikipedia ，在合并之前需要对每 2 个元素部分进行排序。https://en.wikipedia.org/wiki/K-way_merge_algorithm）所以，它也从单个元素开始并合并它们对吗？所以，数组的步骤：8,9,1,6,4

Step1：{8,9} {1,6} {4} [最后是奇元素合并]

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

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

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

标签： algorithmmergesort

Answer 1

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

迭代 2 路归并排序的另一个名称是自下而上归并排序，而递归归并排序的另一个名称是自上而下归并排序。

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

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

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