Python中的遞歸合併排序和堆棧幀

Question

下面的代碼（不是我的，只是學習它）在原始列表（即list_）上遞歸和合並例程之間反彈（正確）。堆棧框架的流程（即，他們如何以及爲什麼以他們的方式返回，目前還不清楚，即使在使用Python Tutor進行觀察時，這也是我在下面敘述的）。描述代碼如何返回以及問題如何跟隨程序。

def merge(left, right): 
    if not len(left) or not len(right): 
     return left or right 

    result = [] 
    i, j = 0, 0 
    while (len(result) < len(left) + len(right)): 
     if left[i] < right[j]: 
      result.append(left[i]) 
      i+= 1 
     else: 
      result.append(right[j]) 
      j+= 1 
     if i == len(left) or j == len(right): 
      result.extend(left[i:] or right[j:]) 
      break 

    return result 

def mergesort(list_): 
    if len(list_) < 2: 
     return list_ 

    middle = len(list_)//2 
    left = mergesort(list_[:middle]) 
    right = mergesort(list_[middle:]) 

    return merge(left, right) 


list_ = [7,5,2,1,3] 

print(mergesort(list_)) 

我們碰到的第一個遞歸調用left（我們要在列表的左半部分進行排序，然後左半邊的左半部分，等等，直到我們得到大小爲一的名單，打基地案件）。這工作正常。我們從[7,5,2,1,3]到[7,5]到[7]並打基礎案例。到現在爲止還挺好。 我期望堆棧幀開始返回，但那不是真的發生了什麼。我認爲它返回7，但是接着我們跳到right的下一組遞歸調用。 5重新出現。 5出現在7之前的堆棧框架中，所以事情以相反的順序返回（這很好）。新參數拆分5並創建單個列表，從而設置基本情況並返回5.

下面是它變得很奇怪的地方：程序進入合併步驟，這是正確的。 它如何「知道」跳過right或left（我給了它一個完整的列表，其中大部分是未觸及過的）進一步遞歸併跳轉到合併？此外，它是如何知道從合併中回到mergesort函數的，而沒有明確的指示，並確切地知道在哪裏拾取？任何人都可以對此有所瞭解嗎？傳統的算法文本和大多數視頻都沒有幫助，因爲它們沒有處理堆棧幀。

Answer 1

我認爲你的困惑與不瞭解每個堆棧幀都有自己的執行點有關。每次調用某個函數時，該幀的執行都會暫停，併爲該函數調用創建一個新幀。當它返回時，前一幀從停止的地方開始拾取。沒有「知道」代碼應該放在哪裏的中心位置，每個級別都處理它自身。

在您所描述的示例場景中，mergesort呼籲[7, 5]第一拆分名單成[7]和[5]，再依次遞歸他們每個人得到left和right。當第二次遞歸調用返回時，它將進入代碼的下一部分，即merge調用，僅僅是因爲代碼中的下一部分。

你可以看到邏輯很清楚，就在這裏：

left = mergesort(list_[:middle]) 
right = mergesort(list_[middle:]) 

return merge(left, right) 

這就告訴你，在這個運行（每不打基本情況運行），這將遞歸兩次，然後merge。