合併排序，遞歸部分

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

一旦列表只包含一個元素，每對葉子都會被排序並加入。然後，您可以遍歷列表並找出下一對應插入的位置。遞歸「知道」沒有什麼關於遞歸遞歸樹，而是具有這種效果的排序和連接行爲。