合并排序，递归部分

Question

在研究合并排序几天之后，我从概念上理解它，但有一件事我没有得到。

我得到什么：

1）它需要一个列表，例如数字数组并分割成两半和排序两个半区，并​​最终将它们合并在一起。

2.）因为它是一个递归算法，所以它使用递归来做到这一点。 所以提到阵列的分裂看起来是这样的：

它，拆分阵列，直到只有一个在各列表项，并通过其视为排序。 。在这一点在 合并的步骤应该是哪一个像这样：

我不明白的是，如何递归“知道”它分裂的所有名单，只有一个项目后在列表中，为了恢复递归树？合并后左侧和右侧如何成为左侧？

困扰我的事情是这样的。我已经采取了代码的快照从interactivepython页

如何代码言归正传，我们已经lefthalf = 2后，和righthalf = 1，编写一个在图片的显示，其中lefthalf = [1,2]和righthalf = [4,3]，而不回到将我们已经合并的递归。

TNX， 汤姆

Answer 1

如果你正在谈论奇数子列表，那么它是依赖于实施。

它每次都会在左侧放置更大的子列表，或者每次放置在右侧。

Answer 2

“递归”当然不知道这一点。它是使用递归，它看起来像这样（有点简单化）的代码：

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

这里你可以看到的是，“递归”（即sort递归调用）不需要“知道”任何东西。他们唯一的工作是提供一个排序列表，数组或其他任何东西。

换一种说法：如果我们有merge满足下列不变：

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

那么我们可以很容易地归并像写上面列出。剩下的事情就是处理简单的情况：空列表，单例列表和带有两个元素的列表。

Answer 3

一旦列表只包含一个元素，每对叶子都会被排序并加入。然后，您可以遍历列表并找出下一对应插入的位置。递归“知道”没有什么关于递归递归树，而是具有这种效果的排序和连接行为。