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

兩路歸并算法

算法基本思路

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

（1）合并過(guò)程

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

（2）動(dòng)態(tài)申請(qǐng) R1

實(shí)現(xiàn)時(shí)，R1 是動(dòng)態(tài)申請(qǐng)的，因?yàn)樯暾?qǐng)的空間可能很大，故須加入申請(qǐng)空間是否成功的處理。

歸并算法

void Merge(SeqList R，int low，int m，int high)  
  {//將兩個(gè)有序的子文件R[low..m)和R[m+1..high]歸并成一個(gè)有序的  
   //子文件R[low..high]  
   int i=low，j=m+1，p=0； //置初始值  
   RecType *R1； //R1是局部向量，若p定義為此類(lèi)型指針?biāo)俣雀? 
   R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))；  
   if(! R1) //申請(qǐng)空間失敗  
     Error("Insufficient memory available!")；  
   while(i<=m&&j<=high) //兩子文件非空時(shí)取其小者輸出到R1[p]上  
     R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]；  
   while(i<=m) //若第1個(gè)子文件非空，則復(fù)制剩余記錄到R1中  
     R1[p++]=R[i++]；  
   while(j<=high) //若第2個(gè)子文件非空，則復(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  

歸并排序

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

自底向上的方法

（1）自底向上的基本思想

自底向上的基本思想是：第 1 趟歸并排序時(shí)，將待排序的文件 R[1..n]看作是 n 個(gè)長(zhǎng)度為 1 的有序子文件，將這些子文件兩兩歸并，若 n 為偶數(shù)，則得到http://wiki.jikexueyuan.com/project/data-structure-sorting/images/i2.gif" alt="" />個(gè)長(zhǎng)度為 2 的有序子文件；若 n 為奇數(shù)，則最后一個(gè)子文件輪空(不參與歸并)。故本趟歸并完成后，前http://wiki.jikexueyuan.com/project/data-structure-sorting/images/i3.gif" alt="" />個(gè)有序子文件長(zhǎng)度為 2，但最后一個(gè)子文件長(zhǎng)度仍為 1；第 2 趟歸并則是將第 1 趟歸并所得到的http://wiki.jikexueyuan.com/project/data-structure-sorting/images/i3.gif" alt="" />個(gè)有序的子文件兩兩歸并，如此反復(fù)，直到最后得到一個(gè)長(zhǎng)度為 n 的有序文件為止。

上述的每次歸并操作，均是將兩個(gè)有序的子文件合并成一個(gè)有序的子文件，故稱(chēng)其為"二路歸并排序"。類(lèi)似地有k(k>2)路歸并排序。

（2） 二路歸并排序的全過(guò)程 【參見(jiàn)動(dòng)畫(huà)演示】

（3） 一趟歸并算法 分析： 在某趟歸并中，設(shè)各子文件長(zhǎng)度為length(最后一個(gè)子文件的長(zhǎng)度可能小于length)，則歸并前R[1..n]中共有http://wiki.jikexueyuan.com/project/data-structure-sorting/images/i3.gif" alt="" />個(gè)有序的子文件：R

[1..length]，R[length+1..2length]，…，http://wiki.jikexueyuan.com/project/data-structure-sorting/images/i4.gif" alt="" /> 。

注意： 調(diào)用歸并操作將相鄰的一對(duì)子文件進(jìn)行歸并時(shí)，必須對(duì)子文件的個(gè)數(shù)可能是奇數(shù)、以及最后一個(gè)子文件的長(zhǎng)度小于 length 這兩種特殊情況進(jìn)行特殊處理：

• 若子文件個(gè)數(shù)為奇數(shù)，則最后一個(gè)子文件無(wú)須和其它子文件歸并(即本趟輪空)；
• 若子文件個(gè)數(shù)為偶數(shù)，則要注意最后一對(duì)子文件中后一子文件的區(qū)間上界是 n。

具體算法如下：

void MergePass(SeqList R，int length)  
     { //對(duì)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)；  
           //歸并長(zhǎng)度為length的兩個(gè)相鄰子文件  
      if(i+length-1<n) //尚有兩個(gè)子文件，其中后一個(gè)長(zhǎng)度小于length  
         Merge(R，i，i+length-1，n)； //歸并最后兩個(gè)子文件  
      //注意：若i≤n且i+length-1≥n時(shí)，則剩余一個(gè)子文件輪空，無(wú)須歸并  
     } //MergePass  

（4）二路歸并排序算法

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

      MergePass(R，length)； //有序段長(zhǎng)度≥n時(shí)終止  
 }  

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

自頂向下的方法

采用分治法進(jìn)行自頂向下的算法設(shè)計(jì)，形式更為簡(jiǎn)潔。

（1）分治法的三個(gè)步驟

設(shè)歸并排序的當(dāng)前區(qū)間是R[low..high]，分治法的三個(gè)步驟是：

• 分解：將當(dāng)前區(qū)間一分為二，即求分裂點(diǎn) http://wiki.jikexueyuan.com/project/data-structure-sorting/images/i5.gif" alt="" />
• 求解：遞歸地對(duì)兩個(gè)子區(qū)間 R[low..mid]和 R[mid+1..high]進(jìn)行歸并排序；
• 組合：將已排序的兩個(gè)子區(qū)間 R[low..mid]和 R[mid+1..high]歸并為一個(gè)有序的區(qū)間 R[low..high]。

遞歸的終結(jié)條件：子區(qū)間長(zhǎng)度為 1（一個(gè)記錄自然有序）。

（2）具體算法

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

（3）算法 MergeSortDC 的執(zhí)行過(guò)程

算法 MergeSortDC 的執(zhí)行過(guò)程如下圖所示的遞歸樹(shù)。

算法分析

1、穩(wěn)定性

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

2、存儲(chǔ)結(jié)構(gòu)要求

可用順序存儲(chǔ)結(jié)構(gòu)。也易于在鏈表上實(shí)現(xiàn)。

3、時(shí)間復(fù)雜度

對(duì)長(zhǎng)度為 n 的文件，需進(jìn)行 趟二路歸并，每趟歸并的時(shí)間為 O(n)，故其時(shí)間復(fù)雜度無(wú)論是在最好情況下還是在最壞情況下均是 O(nlgn)。

4、空間復(fù)雜度

需要一個(gè)輔助向量來(lái)暫存兩有序子文件歸并的結(jié)果，故其輔助空間復(fù)雜度為 O(n)，顯然它不是就地排序。

注意： 若用單鏈表做存儲(chǔ)結(jié)構(gòu)，很容易給出就地的歸并排序。