再帰的マージソートC++

Question

C++で再帰的マージソートプログラムを作成したいと思います。問題は、ベースケースの考え方を再帰的に動作させる方法がわからないことです。誰でもMerg Function()、Split Function()およびMergSort()の基本的なケースが何であるか教えてください。私はあなたに感謝します。

void Merg(int A[], int s1, int e1, int s2, int e2) 
{ 
    int B[8]; 
    int i=0; 

    while (A[s1] < A[s2]) 
     B[i] = B[s1]; 
     i++; 
     s1++; 

     if (s1 == e1) 
     { 
     B[i] = A[s2]; 
     i++; 
     s2++; 
     } 

    while (A[s2] < A[s1]) 
     B[i] = B[s2]; 
     i++; 
     s2++; 

     if (s2 == e2) 
     { 
     B[i] = A[s1]; 
     i++; 
     s1++; 
     } 
} 

void Split(int A[], int s, int e) 
{ 
    int mid = (s+e)/2; 

    if (s < e && mid != 0) 
    { 
     Split(A, s, mid); 
     Split(A, mid+1, e); 
    } 
    Merg(A, s, mid, mid+1, e); 
} 

int main() 
{ 
    int A[8] = {10,4,8,12,11,2,7,5}; 

    Split(A, 0, 7); 

    return 0; 
} 

Answer 1

ベースケースをソートすることが保証されている配列であるので、空の配列または長さの配列のいずれか1

あなたのマージ関数が正しくありませんが、少なくともの大部分を含んでいます正しいアイデア。さらに必要なのは、ラッピングループといくつかの条件があり、マージが配列の最後を過ぎて実行されないようにするだけです。分割関数は完全にオフ、分割は再帰的ではなく、再帰的なmergeSort呼び出しの中でさらに分割が発生します。

1. 長IF（A）< 2リターン//既にマージソート
2. H
3. 分割下半分LにおけるAと上半分をソートL
4. マージソートH
5. マージソートされたLとH
6. が行わ