合并排序，递归部分 [英] Merge sort, the recursion part
问题描述
在研究了几天的合并排序后，我从概念上了解了它，但是我没有一件事.
After studying the merge sort for a couple of days, I understand it conceptually, but there is one thing that I don't get.
我得到的东西:
1.)它获取一个列表，例如一个数字数组，将其分成两半，对两个半数进行排序，最后将它们合并在一起.
1.) It takes a list, for example an array of numbers and splits it in half and sorts the two halfs, and in the end merges them together.
2.)因为它是一种递归算法，所以它使用递归来做到这一点. 因此，提到的数组的拆分看起来像这样:
2.) Because it's an recursive algorithm it uses recursion to do that. So the split of the mentioned array looks like this:
它会拆分数组，直到每个列表中只有一个项目并按其排序为止.然后合并就开始了. 看起来应该像这样:
It, splits the array until there is only one item in each list and by that its considered sorted. And at that point the merge steps in. Which should look like this:
我没有得到的是，递归将所有列表拆分为列表中的一个项目后，如何知道"以恢复递归树?左侧和右侧的东西合并后如何变成左侧?
What I don't get is, how does the recursion "know" after it splits all the lists to only one item in a list, to get back up the recursion tree? How does something that has a left and right side become the left side after it merges?
困扰我的是这个.我已经从InteractivePython页面拍摄了代码快照
The thing that bothers me is this. I've taken a snapshot of the code from interactivepython page
在我们将lefthalf = 2和righthalf = 1后，代码如何到达图中所示的代码，其中lefthalf = [1,2]和righthalf = [4,3]，而没有回到将划分我们合并内容的递归?
How does the code get to the point, after we have lefthalf = 2, and righthalf = 1, to to code that's shown in the picture where the lefthalf = [1,2] and righthalf = [4,3] without going back to the recursion that would divide what we have have merged?
Tnx， 汤姆
推荐答案
一旦列表仅包含一个元素，就对每对叶子进行排序和连接.然后，您可以遍历列表，找出应该在下一对插入的位置.递归不知道"关于返回递归树的任何信息，而是排序和连接的行为才具有这种效果.
Once the list only contains one element, each pair of leaves are sorted and joined. Then you can traverse through the list and find out where the next pair should be inserted. The recursion "knows" nothing about going back up the recursion tree, rather it is the act of sorting and joining that has this effect.
这篇关于合并排序，递归部分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
