在this SO answer中，有一個計算長度爲32（最差情況）的數組的併發遞歸調用數的示例：1 + 2 + 4 + 8 + 16 + 32 = 63。Mergesort - 遞歸調用的最大數目
想象爲什麼會這樣 - 在樹的每一層都有2個節點的功率，我們總是進入下一層直到最後一層。
我想知道如何計算這個數字（遞歸調用的最大數量）爲任意長度的數組n？實際上，這個數字似乎是2*n-1，但我不明白爲什麼。有人可以解釋它背後的邏輯嗎？
讓我們來看看模式。
如果n = 1有一個單一的電話（沒有任何關係）。
如果是n真的，那麼對我們的2n第一次調用將其劃分爲n和n，每一個我們在排序來電2n-1爲4n-2更多。所以我們需要1 + 4n-2 = 4n - 1 = 2*(2n)-1，結果成立。
如果是爲了n和n+1真然後2n+1我們的第一個電話將其劃分爲n和n+1。我們用另一個2n-1和2(n+1)-1 = 2n+1調用排序。撥打1 + 2n-1 + 2n+1 = 4n + 1 = 2*(2n+1) - 1致電。
因此，因爲它對於1是正確的，所以對於2是正確的。因爲它對於1和2是正確的，所以對於3是正確的。因爲它對於2是正確的，對於4是正確的。因爲對於2是正確的以及3對於5是對的。等等。
您可以輕鬆地將其轉化爲強大的歸納法，並將其轉化爲正式的證明。