C++ 歸併排序算法錯誤分析：數據歸零問題修復

歸併排序是經典的分治算法，但實現時極易出現邊界條件錯誤。本文分析一段有缺陷的 C++ 歸併排序代碼，找出導致數據歸零的根因並給出修正版本。

原始代碼問題現象

運行後發現排序結果中大量數據變為 0，且非預期行為。

核心錯誤定位

經分析，問題出在 main() 函數中調用 merge() 前，未將原始數據複製到臨時數組 tearr。導致歸併過程中讀取未初始化的內存（全局數組默認初始化為 0），污染排序結果。

關鍵修正代碼

void main() {
  int i;
  // 初始化原始數據
  for (i = 0; i < MAX; i++) {
    arr[i] = rand();
  }
  // 打印原始數據
  for (i = 0; i < MAX; i++) printf("%d ", arr[i]);
  system("pause");

  /***** 關鍵修正：將原始數據複製到臨時數組 *****/
  for (i = 0; i < MAX; i++) {
    tearr[i] = arr[i];
  }
  /***** 缺少此步導致歸併讀取到全局零值 *****/

  merge(arr, tearr, 0, MAX - 1);

  // 輸出排序結果
  for (i = 0; i < MAX; i++) {
    printf(" %d", arr[i]);
  }
  system("pause");
}

歸併函數邏輯說明

merge() 遞歸將區間 [lhead, rtail] 二分，歸併時將有序子區間合併到臨時數組 t[]，再拷貝回 a[]。關鍵點：

• 臨時數組 t[] 必須包含待排序數據的初始副本
• 拷貝回寫時應只覆蓋當前區間 [lhead, rtail]，而非整個 MAX 範圍（原代碼 for(b=0;b 存在越界風險）