MergeSort without merge function ,,這個算法如何合併列表

Question

def mergeSort(A): 
    if len(A) < 2: 
     return A 

    mid = int(len(A)/2) 
    left = mergeSort(A[:mid]) 
    right = mergeSort(A[mid:]) 

    r,l = 0,0 
    B = [] 

    while len(B) < len(A): 
     if r >= len(right) or (l < mid and left[l] < right[r]): 
      B.append(left[l]) 
      l += 1 
     elif r < len(right): 
      B.append(right[r]) 
      r += 1 

    return B 

print(mergeSort([4,3,6,9,8,5,1])) 

我對上述程序的懷疑是如何在沒有單獨的合併函數的情況下合併列表？

到底遞歸函數調用後，我覺得left和right列表包含每個只有一個元素......他們進行排序，並插入使用while循環列出B ......那麼其他的元素..因爲在這裏while循環只執行一次，以及如何將列表A再次分割和合並...我在互聯網上獲得了這個程序，它工作得很好。

Answer 1

我認爲您的問題是您不明白遞歸如何工作。 while循環不僅執行一次，而且每次（非平凡）遞歸調用執行一次。

這是值得通過操作跟蹤。無論是在紙上，在調試器中使用this one這樣的圖形化可視化工具，還是隻使用一堆print調用，都是您真正瞭解到底發生了什麼的唯一方法。

我認爲圖形化可視化器會更容易遵循，但學習如何在紙上做到這一點是值得的，所以讓我們來做。我們只需要通過一個非平凡的合併，因爲在那之後它們看起來都是一樣的。

• 排序[4,3,6,9,8,5,1]
  • 排序[4,3,6]
  • 排序[4]
  • 由於[4]長度爲0或1，平凡排序它通過只返回它原樣。
  • 排序[3, 6]
  • 排序[3]
    • 由於[3]長度爲0或1，平凡排序它通過只返回它原樣。
  • 排序[6]
    • 由於[6]長度爲0或1，平凡排序它通過只返回它原樣。
  • 合併排序[3]和[6]半部（如果您使用圖形可視化，這發生在步驟31;如果使用調試器，將斷點處線12，這將在第一時間斷點是命中）：
    • 開始l, r, B = 0, 0, []
    • 由於len([]) < len([3, 6])，我們還沒有完成。
    • 由於第一個if條件成立，因此從left開始追加並且遞增l，因此l, r, B = 1, 0, [3]。
    • 由於len([3]) < len([3, 6])，我們沒有完成。
    • 由於第一個if條件爲假，第二個爲真，從right追加並增加r，所以l, r, B = 1, 1, [3, 6]。
    • 由於len([3, 6]) == len([3, 6])，我們完成了。
  • 將排序後的[4]和[3, 6]合併爲上述的相同方式。
• 排序[9, 8, 5, 1]。
  • 這正好在與上述相同，並將包括平凡返回4單元素列表，加上使用while環合併[9]和[8]，和[5]和[1]，和[8, 9]沿途[1, 5];如果你不明白它是如何工作的，你可以自己一步步細節。
• 將排序的[3, 4, 6]和[1, 5, 8, 9]合併爲上述的相同方式。

正如您所看到的，while循環實際上執行了六次，而不僅僅是一次。

Answer 2

執行while循環之前，我們有兩個有序列表中left和right 什麼while循環的作用是要經過在列表中left和right順序每個元素並插入較小的元素融入到一個空列表B，和它由mergesort函數返回。

我們不需要調用單獨

合併功能，例如，考慮列表[3,1,2] 的通話將是：

mergesort([3,1,2]) 
left = mergesort([3]) -> [3] 
right = mergesort([1,2]) -> [1,2] #magically 

B = [] 

while循環採l次/ r左/右的元素取決於哪一個較小，並且分別遞增l/r，並將該元素插入B

B -> [1,2,3] 

嘗試在紙上運行mergesort（[1,2]）的while循環以瞭解right如何變爲[1,2]