歸并排序(Merge Sort)是利用"歸并"技術(shù)來進行排序。歸并是指將若干個已排序的子文件合并成一個有序的文件。

1、算法基本思路
    　設(shè)兩個有序的子文件(相當(dāng)于輸入堆)放在同一向量中相鄰的位置上：R[low..m]，R[m+1..high]，先將它們合并到一個局部的暫存向量R1(相當(dāng)于輸出堆)中，待合并完成后將R1復(fù)制回R[low..high]中。

（1）合并過程
    　合并過程中，設(shè)置i，j和p三個指針，其初值分別指向這三個記錄區(qū)的起始位置。合并時依次比較R[i]和R[j]的關(guān)鍵字，取關(guān)鍵字較小的記錄復(fù)制到R1[p]中，然后將被復(fù)制記錄的指針i或j加1，以及指向復(fù)制位置的指針p加1。
    　重復(fù)這一過程直至兩個輸入的子文件有一個已全部復(fù)制完畢(不妨稱其為空)，此時將另一非空的子文件中剩余記錄依次復(fù)制到R1中即可。

（2）動態(tài)申請R1
    　實現(xiàn)時，R1是動態(tài)申請的，因為申請的空間可能很大，故須加入申請空間是否成功的處理。

2、歸并算法
  void Merge(SeqList R，int low，int m，int high)
    {//將兩個有序的子文件R[low..m)和R[m+1..high]歸并成一個有序的
     //子文件R[low..high]
     int i=low，j=m+1，p=0； //置初始值
     RecType *R1； //R1是局部向量，若p定義為此類型指針速度更快
     R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))；
     if(! R1) //申請空間失敗
       Error("Insufficient memory available!")；
     while(i<=m&&j<=high) //兩子文件非空時取其小者輸出到R1[p]上
       R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]；
     while(i<=m) //若第1個子文件非空，則復(fù)制剩余記錄到R1中
       R1[p++]=R[i++]；
     while(j<=high) //若第2個子文件非空，則復(fù)制剩余記錄到R1中
       R1[p++]=R[j++]；
     for(p=0，i=low；i<=high；p++，i++)
       R[i]=R1[p]；//歸并完成后將結(jié)果復(fù)制回R[low..high]
    } //Merge

   歸并排序有兩種實現(xiàn)方法：自底向上和自頂向下。

1、 自底向上的方法
（1） 自底向上的基本思想
     自底向上的基本思想是：第1趟歸并排序時，將待排序的文件R[1..n]看作是n個長度為1的有序子文件，將這些子文件兩兩歸并，若n為偶數(shù)，則得到 個長度為2的有序子文件；若n為奇數(shù)，則最后一個子文件輪空(不

參與歸并)。故本趟歸并完成后，前 個有序子文件長度為2，但最

后一個子文件長度仍為1；第2趟歸并則是將第1趟歸并所得到的 個有

序的子文件兩兩歸并，如此反復(fù)，直到最后得到一個長度為n的有序文件為止。
     上述的每次歸并操作，均是將兩個有序的子文件合并成一個有序的子文件，故稱其為"二路歸并排序"。類似地有k(k>2)路歸并排序。

（2） 二路歸并排序的全過程 (略)
 
（3） 一趟歸并算法
 分析：
      在某趟歸并中，設(shè)各子文件長度為length(最后一個子文件的長度可能小于length)，則歸并前R[1..n]中共有 個有序的子文件：R

[1..length]，R[length+1..2length]，…， 。
注意：
     調(diào)用歸并操作將相鄰的一對子文件進行歸并時，必須對子文件的個數(shù)可能是奇數(shù)、以及最后一個子文件的長度小于length這兩種特殊情況進行特殊處理：
　?、?若子文件個數(shù)為奇數(shù)，則最后一個子文件無須和其它子文件歸并(即本趟輪空)；
　?、?若子文件個數(shù)為偶數(shù)，則要注意最后一對子文件中后一子文件的區(qū)間上界是n。

  具體算法如下：
    void MergePass(SeqList R，int length)
     { //對R[1..n]做一趟歸并排序
      int i；
      for(i=1;i+2*length-1<=n;i=i+2*length)
      Merge(R，i，i+length-1，i+2*length-1)；
           //歸并長度為length的兩個相鄰子文件
      if(i+length-1<n) //尚有兩個子文件，其中后一個長度小于length
         Merge(R，i，i+length-1，n)； //歸并最后兩個子文件
      //注意：若i≤n且i+length-1≥n時，則剩余一個子文件輪空，無須歸并
     } //MergePass

（4）二路歸并排序算法
  void MergeSort(SeqList R)
   {//采用自底向上的方法，對R[1..n]進行二路歸并排序
     int length；
     for(1ength=1；length<n；length*=2) //做 趟歸并

        MergePass(R，length)； //有序段長度≥n時終止
   }

注意：
     自底向上的歸并排序算法雖然效率較高，但可讀性較差。

2、自頂向下的方法
     采用分治法進行自頂向下的算法設(shè)計，形式更為簡潔。

（1）分治法的三個步驟
     設(shè)歸并排序的當(dāng)前區(qū)間是R[low..high]，分治法的三個步驟是：
①分解：將當(dāng)前區(qū)間一分為二，即求分裂點
                
②求解：遞歸地對兩個子區(qū)間R[low..mid]和R[mid+1..high]進行歸并排序；
③組合：將已排序的兩個子區(qū)間R[low..mid]和R[mid+1..high]歸并為一個有序的區(qū)間R[low..high]。
  遞歸的終結(jié)條件：子區(qū)間長度為1（一個記錄自然有序）。

（2）具體算法
    void MergeSortDC(SeqList R，int low，int high)
     {//用分治法對R[low..high]進行二路歸并排序
       int mid；
       if(low<high){//區(qū)間長度大于1
          mid=(low+high)/2； //分解
          MergeSortDC(R，low，mid); //遞歸地對R[low..mid]排序
          MergeSortDC(R，mid+1，high)； //遞歸地對R[mid+1..high]排序
          Merge(R，low，mid，high)； //組合，將兩個有序區(qū)歸并為一個有序區(qū)
        }
     }//MergeSortDC

（3）算法MergeSortDC的執(zhí)行過程 (略)
     算法MergeSortDC的執(zhí)行過程如下圖所示歸樹。    
二、算法分析

1、穩(wěn)定性
     　歸并排序是一種穩(wěn)定的排序。

2、存儲結(jié)構(gòu)要求
    　可用順序存儲結(jié)構(gòu)。也易于在鏈表上實現(xiàn)。

3、時間復(fù)雜度
    　對長度為n的文件，需進行 趟二路歸并，每趟歸并的時間為O(n)，故其時間復(fù)雜度無論是在最好情況下還是在最壞情況下均是O(nlgn)。

4、空間復(fù)雜度
   　 需要一個輔助向量來暫存兩有序子文件歸并的結(jié)果，故其輔助空間復(fù)雜度為O(n)，顯然它不是就地排序。
  注意：
    　若用單鏈表做存儲結(jié)構(gòu)，很容易給出就地的歸并排序