爲什麼執行mergesort的代碼不能產生正確的結果？

Question

在這裏我試圖在10個元素的數組上實現mergesort。在提供輸入[10] = {9,8,7,6,5,4,3,2,1,0}時，我得到輸出爲{0,0,1,1,0，4,4 ，4,3,2}，而預期產出爲{0,1,2,3,4,5,6,7,8,9}。我在main中調用mergesort，l = 0，h = 9。

void mergesort(int a[],int l,int h) 
    { 
     int c[10]; 
     int m=(l+h)/2; 
     if(l<h) 
     { 
      mergesort(a,l,m);   // Recursive call to sort first half 
      mergesort(a,m+1,h);   // Recursive call to sort second half 
     } 
     int i,k=l,j=l; 
     while(k<=h)      // Merging the first and second half of the array 
     { 
      if(a[j]<a[m+1]) 
      { 
       c[k]=a[j]; 
       k++; 
       j++; 
      } 
      else 
      { 
       c[k]=a[m+1]; 
       k++; 
       m++; 
      }  
     } 
     for(i=l;i<=h;i++) 
      a[i]=c[i]; 
    } 

Answer 1

爲數不多的問題：你的l值不再while循環，因爲你是遞增之後有效的左極限。因此，當您在for循環中稍後從數組c複製到a時，您正在複製無效數據。

Answer 2

問題是，在你的while循環中，你有時會看到你應該在的界限之外。

假設你在你的函數的開始處插入一個檢查，說明如果l == h然後返回（因爲不需要對一個元素數組進行排序），那麼當它第一次執行任何操作時，它會返回到mergesort(a, 0,1)。這裏我們基本上合併了兩個單元素數組。

通過你的循環會在第一時間，我們有i,j,k,m=0當。我們將進入if的else部分，因爲元素0大於1.因此，我們將[1]寫入輸出數組，現在我們有i,j=0和k,m=1。我們現在應該做的是注意我們的第二個數組已耗盡，並從第一個數組中的其餘元素中填充。

取而代之的是比較元素j和m+1（即0和2）。這顯然是錯誤的，因爲元素2不應出現在數組中。我們當然發現元素2較小，因此將其放置在位置2的輸出數組中。一旦我們複製這個，我們得到{8, 7, 7, 6, 5, 4, 3, 2, 1, 0}，這是一切都出錯了。