归并排序不是在所有情况下

Question

我已经写了如下合并排序的代码工作：

#include <stdio.h> 

void mergeSort(int array[],int left, int right); 

void mergeArray(int array[],int left,int middle, int right); 

void mergeArray(int array[],int left,int middle, int right) 
{ 

    int n1 = middle - left + 1; 
    int n2 = right - middle ; 

    int temp_a[n1]; 
    int temp_b[n2]; 

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

    for (i = left ; i <= middle ; i++) 
    { 
     temp_a[k++] = array[i]; 
    } 

    for (i = middle + 1 ; i < right + 1; i++) 
    { 
     temp_b[j++] = array[i]; 
    } 

    // now merge these two arrays 


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


    while (i < n1 && j < n2) 
    { 
     if (temp_a[i] < temp_b[j]) 
     { 
      array[k++] = temp_a[i++]; 

     } 
     else 
     { 
      array[k++] = temp_b[j++]; 
     } 
    } 

    while (i < n1) 
    { 
     array[k++] = temp_a[i++];  
    } 

    while (j < n2) 
    { 
     array[k++] = temp_b[j++]; 
    } 



} 


void mergeSort(int array[],int left, int right) 
{ 
    // since there is only one element in the array. 
    printf("I am in merge sort. left : %d, right : %d\n",left,right); 
    if (right - left < 1) 
    { 
     return; 
    } 
    else 
    { 
     int middle = (right - left)/2 ; 
     mergeSort(array,left, middle);  
     mergeSort(array, middle +1 , right); 

     mergeArray(array,left,middle,right); 
    } 


} 

int main(int argc, char const *argv[]) 
{ 
    int n = 3; 
    int i; 

    int array[] = { 12,11,14,19}; 

    mergeSort(array,0,n); 
    printf("\nArray is: \n"); 

    for (i = 0; i <= n; ++i) 
    { 
     printf("%d\n",array[i]); 
    } 
    return 0; 
} 

上面的代码工作n = 1和n = 2但不能为其它的值。

Answer 1

三个问题：（1）在mergeArray中，您使用n1代替n2代替temp_b。将其更改为：

int temp_b[n2]; 

（2）创建temp_a和temp_b，注释后 “现在合并这两个数组” 后，您需要设置k到left，而不是0：

k = left; 

（ 3）在mergeSort中，您的表达式为middle不正确，您需要添加而不是减去：

int middle = (right + left)/2 ; 

它应该与这三个变化一起工作。