有人能告訴我我的mergesort有什麼問題嗎？

Question

有人能告訴我下面的mergesort實現有什麼問題嗎？我一直在抓我的頭幾個小時..

void merge(int arr[], int low, int mid, int high) 
{ 
    int i = 0; 
    int j = 0; 
    int k = 0; 

    int buf1[1024]; 
    int buf1Length = mid - low + 1; 

    int buf2[1024]; 
    int buf2Length = high - (mid + 1) + 1; 

    for (i = low; i <= mid; i++) 
    { 
     buf1[j++] = arr[i]; 
    } 

    for (i = mid + 1; i <= high; i++) 
    { 
     buf2[k++] = arr[i]; 
    } 

    i = 0; 
    j = 0; 
    k = 0; 

    while (j < buf1Length && k < buf2Length) 
    { 
     if (buf1[j] <= buf2[k]) 
     { 
      arr[i++] = buf1[j++]; 
     } 
     else 
     { 
      arr[i++] = buf2[k++]; 
     } 
    } 

    while (j < buf1Length) 
     arr[i++] = buf1[j++]; 

    while (k < buf2Length) 
     arr[i++] = buf2[k++]; 
} 

void mergeSort(int arr[], int low, int high) 
{ 
    int mid; 

    if (low < high) 
    { 
     mid = (low + high)/2; 
     mergeSort(arr, low, mid); 
     mergeSort(arr, mid + 1, high); 
     merge(arr, low, mid, high); 
    } 
} 

int main() 
{ 
    int i; 
    int arr[] = {6, 7, 2, 4, 9, 8}; 
    mergeSort(arr, 0, 5); 

    printf("\n\n results: \n"); 
    for (i = 0; i < 6; i++) 
    { 
     printf("%d ", arr[i]); 
    } 
    printf("\n\n\n"); 

    return 0; 
} 

Answer 1

你確定你想要做的：

i = 0; 
j = 0; 
k = 0; 

？

乍一看，我覺得應該是：

i = low; 
j = 0; 
k = 0; 

Answer 2

必須歸併排序合併亞：

a = 1,3,5 
b = 2,4,6 
c = merge(a, b) // C = 1,2,3,4,5,6 

您沒有任何的排序序列。

Answer 3

這個問題毫無疑問在你的merge()函數中。

我會想象合併功能會是這樣的（這裏的任何錯誤都留給讀者：X ...這是未經測試和即興，並應使用僅用於展示概念！）：

/** 
* let mid be the last element of the first array 
* making mid + 1 the first element of the second 
*/ 
merge(int[] arr, int low, int mid, int high) { 

    int[] buff; 
    int lowpos; 
    int highpos; 
    int i; 

    buff = new int[high - low + 1]; 
    lowpos = low; 
    highpos = mid + 1; 

    // merge the two subarrays into the buffer 
    for(i = 0; i < (high - low + 1); i++) { 
    if(lowpos > mid) buff[i] = arr[highpos++]; 

    else if(highpos > high) buff[i] = arr[lowpos++]; 

    else if(arr[lowpos] < arr[highpos] buff[i] = arr[lowpos++]; 

    else buff[i] = arr[highpos++]; 
    } 

    // copy the buffer back into the main array 
    for(i = 0; i < (high - low + 1) i++) arr[i+low] = buff[i]; 
}