归并排序，递归部分

Question

研究了几天归并排序，从概念上理解了，但是有一点不懂。

我得到的：

1.) 它接受一个列表，例如一个数字数组，并将其分成两半并对两半进行排序，最后将它们合并在一起。

2.) 因为它是一种递归算法，所以它使用递归来实现。所以上述数组的拆分看起来像这样：

它拆分数组，直到每个列表中只有一个项目，并据此认为它已排序。就在那时，合并介入了。应该是这样的：

我不明白的是，递归 "know" 在将所有列表拆分为列表中的一个项目后如何恢复递归树？有左右边的东西合并后怎么变成左边了？

困扰我的是这个。我从 interactivepython 页面截取了代码快照

在左半边 = 2 和右半边 = 1 之后，代码如何达到图中所示的代码，其中左半边 = [1,2] 和右半边 = [4,3 ] 不返回将划分我们已合并的内容的递归？

谢谢，汤姆

Answer 1

如果您谈论的是奇数子列表，则取决于实现。

每次都将较大的子列表放在左边，或者每次都放在右边。

Answer 2

"recursion" 当然对这些一无所知。它是使用递归的代码，看起来像这样（有点简化）：

sort list = merge (sort left_half) (sort right_half)
    where
         (left_half, right_half) = split list

在这里您可以看到 "recursion"（即 sort 的递归调用）不需要 "know" 任何东西。他们唯一的工作是提供排序列表、数组或其他任何东西。

换句话说：如果我们有 merge 满足以下不变量：

1. `merge`, given two sorted lists, will return a sorted list.

然后我们可以像上面概述的那样轻松编写合并排序。排序中剩下要做的是处理简单的情况：空列表、单例和包含两个元素的列表。

Answer 3

一旦列表只包含一个元素，每对叶子就会被排序和连接。然后你可以遍历列表并找出下一对应该插入的位置。递归 "knows" 与返回递归树无关，而是具有这种效果的排序和连接行为。

Merge sort, the recursion part