关于合并排序代码中的合并步骤的混淆

Question

关于数组上的合并排序是如何工作的，我有一个问题。我理解“划分”步骤，它将输入数组划分为1长元素。然而，当涉及到“合并”部分(合并步骤)时，我感到困惑。例如，给定输入3 5 1 8 2，除法过程将产生5种元素: 3, 5，1, 8，2。我只知道合并函数会将它们合并到3 5，1 8，2，但它如何继续合并3 5和1 8？在“组合”部分中是否涉及递归？

Answer 1

当两个递归排序例程返回时，您可以安全地假设它们已经对它们的部分进行了排序。合并步骤组合了这两个排序子数组。如果输入为3 5 1 8 2，则第一个递归调用对前半部分进行排序并生成3 5，第二个递归调用对下半部分进行排序并生成1 2 8。

您询问的合并步骤通过反复选择两个子数组的前两个元素中的最小值并将其添加到结果中，将这两个排序的半部合并为一个部分，如下面的动画所示：

​

​

Answer 2

这个动画应该对你有帮助。

http://en.wikipedia.org/wiki/File:Merge-sort-example-300px.gif

这一过程如下：

3 5 1 8 2

3、5、1、8、2

3 5，1 2 8

1 2 3 5 8

1. 从n个输入项的未排序列表i开始。
2. 把我分成两半: I1和I2，有上限(n/2)和地板(n/2)。
3. 递归排序I1，生成排序列表S1。
4. 递归排序I2，生成排序列表S2。
5. 将S1和S2合并到排序列表S中。

在每次迭代时，从两个输入列表中选择具有最小键的项，并附加到输出列表中。由于对两个输入列表进行了排序，因此只有两个项需要测试，因此每次迭代都需要恒定的时间。