不一致リストを生成するトップダウンマージソートアルゴリズム

Question

トップダウンマージソートアルゴリズムをwikipedia pageから取得してCコードにしましたが、正しい結果が得られませんでした。ここ

はコードです：

#include <stdio.h> 

int A[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; 
int B[10]; //sorted array 
int n; 
void TopDownMergeSort(int A[], int B[],int n); 
void TopDownSplitMerge(int B[], int iBegin, int iEnd, int A[]); 
void TopDownMerge(int A[], int iBegin, int iMiddle, int iEnd, int B[]); 
void CopyArray(int A[], int iBegin, int iEnd, int B[]); 

int main() 
{ 
    TopDownMergeSort(A, B, 10); 
    for(int i = 0;i < 10;i++) { 
     printf("%i ", B[i]); 
    } 
    printf("\n"); 
    return 0; 
} 

// Array A[] has the items to sort; array B[] is a work array. 
void TopDownMergeSort(int A[], int B[], int n) 
{ 
    CopyArray(A, 0, n, B);   // duplicate array A[] into B[] 
    TopDownSplitMerge(B, 0, n, A); // sort data from B[] into A[] 
} 

// Sort the given run of array A[] using array B[] as a source. 
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set). 
void TopDownSplitMerge(int B[], int iBegin, int iEnd, int A[]) 
{ 
    if(iEnd - iBegin < 2)      // if run size == 1 
     return;         // consider it sorted 
    // split the run longer than 1 item into halves 
    int iMiddle = (iEnd + iBegin)/2;    // iMiddle = mid point 
    // recursively sort both runs from array A[] into B[] 
    TopDownSplitMerge(A, iBegin, iMiddle, B); // sort the left run 
    TopDownSplitMerge(A, iMiddle, iEnd, B); // sort the right run 
    // merge the resulting runs from array B[] into A[] 
    TopDownMerge(B, iBegin, iMiddle, iEnd, A); 
} 
void TopDownMerge(int A[], int iBegin, int iMiddle, int iEnd, int B[]) 
{ 
// Left source half is A[ iBegin:iMiddle-1]. 
// Right source half is A[iMiddle:iEnd-1 
    // While there are elements in the left or right runs... 
    for (int k = iBegin; k < iEnd; k++) { 
     // If left run head exists and is <= existing right run head. 
     if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) { 
      B[k] = A[i]; 
      i = i + 1; 
     } else { 
      B[k] = A[j]; 
      j = j + 1;  
     } 
    } 
    printf("Sort result 1: "); 
    for(int i = 0; i < 10; i++) { 
     printf("%i ", A[i]); 
    } 
    printf("\n"); 
} 

void CopyArray(int A[], int iBegin, int iEnd, int B[]) 
{ 
    for(int k = iBegin; k < iEnd; k++) 
     B[k] = A[k]; 
} 

与えられたリストに、このコードを実行する結果6, 7, 8, 9, 10, 1, 2, 3, 4, 5を生成し、一般的に与えられたリストを実行すると、マージされていない2つのソートの半分を持つリストを生成します。できるだけ忠実にアルゴリズムを再現しようとしましたが、どこに問題が発生するのか分からないようです。

Answer 1

Wikipediaの記事のコードにはバグがあります。 TopDownMergeSortで

、ライン：

TopDownSplitMerge(B, 0, n, A); // sort data from B[] into A[] 

は間違っています。 A[]が送信元、B[]が送信先です。これは、修正されたコード行です。

TopDownSplitMerge(A, 0, n, B); // sort data from A[] into B[]