MergeSort中的兩個遞歸調用是什麼？

Question

研究算法並且難以理解具體構成MergeSort中兩個遞歸調用的內容。幫助表示讚賞。謝謝。

Answer 1

讓陣列的大小爲否。基本上取數組並分成兩部分，形成1到N/2和N/2 + 1到N。我們分別稱這些部件爲L和R。現在，如果我們可以將L 和R分開，我們可以將它們合併以得到最終結果。現在你怎麼分類L和R ，再次適用相同的程序。因此有兩個遞歸部分，一個遞歸排序L 和oe兩個遞歸排序R之後它們被合併。 Th僞代碼

 merge_sort (1 , N) 
     merge_sort(1,N/2) /* L */ 
     merger_sort(N/2 + 1,N) /* R */ 
     merge both these sorted parts 

Answer 2

只有一個函數可以實現同樣的功能。 這裏是僞代碼：

def mergesort(int l, int r) { 

    if l == r: 
    return 

    int mid = (l + r)/2 
    mergesort(l, mid) 
    mergesort(mid + 1, r) 

    merge left subarray and right subarray 
} 

這裏是C++代碼：

#include <cstdio> 
#include <cstdlib> 

using namespace std; 
const int N = 1000003; 

int tmp[N]; 
int a[N]; 

void merge_sort(int b, int e) { 

    if(b == e) // if there is only one element, then we have an sorted subarray 
    return; 

    int mid = (b + e)/2; 
    merge_sort(b, mid); //recursive call 
    merge_sort(mid + 1, e); //recursive call 

    int sz = e - b + 1; // the size of the subarray 

    for(int k = 0, i = b, j = mid + 1; k < sz; ++k) { 

    if(i > mid) //if we have passed the border of left subarray, use the right one 
     tmp[k] = a[j++]; 
    else if(j > e) // if we have passed the border of right subarray, use the left one 
     tmp[k] = a[i++]; 
    else { // if all borders are oke 
     if(a[i] > a[j]) // compare values in left and right subarray 
     tmp[k] = a[j++]; 
     else 
     tmp[k] = a[i++]; 
    } 
    } 

    // sorted values form b to e are in tmp array, now just copy the tmp array to array a 
    for(int i = 0, j = b; i < sz; ++i, ++j) 
    a[j] = tmp[i]; 

} 

int main() { 

    int n; scanf("%d", &n); 
    for(int i = 0; i < n; ++i) 
    scanf("%d", &a[i]); 

    merge_sort(0, n - 1); 

    for(int i = 0; i < n; ++i) 
    printf("%d ", a[i]); 

    return 0; 
}