瞭解mergesort-like算法中的遞歸

我想知道這個遞歸算法的流程是如何工作的：an inversion counter based on merge-sort。當我查看merge-sort遞歸樹的圖時，它看起來相當清晰;我認爲葉子會一直分裂，直到每片葉子是一個單元，然後merge()將開始合併它們;因此，開始「移回」樹 - 可以這麼說。瞭解mergesort-like算法中的遞歸

但在下面的代碼，如果我們打印出此功能與給定數組print(sortAndCount(test_case))那麼我們實際上得到來自merge()功能，而不是在sortAndCount() return語句我們的「最終」輸出？所以在下面的代碼中，我認爲sortAndCount()方法會在(invCountA, A) = sortAndCount(anArray[:halfN])中反覆調用它自己，直到達到基本情況，然後繼續處理數組的下一半 - 但現在看起來不正確。有人能糾正我對這種遞歸流的理解嗎？（鈮我截斷部分代碼爲merge()方法，因爲我只關心的遞歸過程。）

def sortAndCount(anArray): 
    N = len(anArray) 
    halfN = N // 2 

    #base case: 
    if N == 1: return (0, anArray)   

    (invCountA, A) = sortAndCount(anArray[:halfN]) 
    (invCountB, B) = sortAndCount(anArray[halfN:]) 
    (invCountCross, anArray) = merge(A, B) 

    return (invCountA + invCountB + invCountCross, anArray) 

def merge(listA, listB): 
    counter = 0 
    i, j = 0, 0 

    #some additional code... 
    #... 
    #... 


    #If all items in one array have been selected, 
    #we just return remaining values from other array: 
    if (i == Asize):         
     return (counter, output_array + listB[j:]) 
    else: 
     return (counter, output_array + listA[i:])

來源

2015-02-06 Eyeofpie

邏輯與mergesort相同，唯一的區別是我們通過計算剩餘在左側的項目來計算分割反轉，當我們找到右側較小的元素時。 – 2015-02-06 17:51:31

你問關於拆分倒置或mergesort？ – 2015-02-06 18:27:15

嗯，我正在問這個[split-inversions]，但正如你所說，它與mergesort非常相似。我的問題是我試圖展開遞歸調用。關鍵是我不知道在行'（invCountA，A）= sortAndCount（anArray [：halfN]）''上發生了什麼。解釋器在繼續之前是否停止計算遞歸的每個級別 - 即它是否通過'（invCountA，A）= sortAndCount（anArray [：halfN]）完成遞歸，直到它達到N大小1，還是創建佔位符，同時繼續通過代碼（只有然後通過遞歸的每個級別）？ – Eyeofpie 2015-02-06 19:19:37

以下圖像創建使用rcviz示出了遞歸調用的順序，作爲文檔中說明邊按照執行遍歷的順序進行編號。邊的顏色從黑到灰表示遍歷順序：先黑邊，後邊是灰邊。：

enter image description here

因此，如果我們遵循的步驟緊密我們可以看到，我們首先遍歷原始數組的左半部分則完全正確的。

來源

2015-02-07 17:35:02

瞭解mergesort-like算法中的遞歸

回答

相關問題