歸并排序(Merge Sort)是利用"歸并"技術來進行排序。歸并是指将若幹個已排序的子檔案合并成一個有序的檔案。
1、算法基本思路
設兩個有序的子檔案(相當于輸入堆)放在同一向量中相鄰的位置上：R[low..m]，R[m+1..high]，先将它們合并到一個局部的暫存向量R1(相當于輸出堆)中，待合并完成後将R1複制回R[low..high]中。
（1）合并過程
合并過程中，設定i，j和p三個指針，其初值分别指向這三個記錄區的起始位置。合并時依次比較R[i]和R[j]的關鍵字，取關鍵字較小的記錄複制到R1[p]中，然後将被複制記錄的指針i或j加1，以及指向複制位置的指針p加1。
重複這一過程直至兩個輸入的子檔案有一個已全部複制完畢(不妨稱其為空)，此時将另一非空的子檔案中剩餘記錄依次複制到R1中即可。
（2）動态申請R1
實作時，R1是動态申請的，因為申請的空間可能很大，故須加入申請空間是否成功的處理。
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個子檔案非空，則複制剩餘記錄到R1中
R1[p++]=R[i++]；
while(j<=high) //若第2個子檔案非空，則複制剩餘記錄到R1中
R1[p++]=R[j++]；
for(p=0，i=low；i<=high；p++，i++)
R[i]=R1[p]；//歸并完成後将結果複制回R[low..high]
} //Merge
歸并排序有兩種實作方法：自底向上和自頂向下。
1、 自底向上的方法
（1） 自底向上的基本思想
自底向上的基本思想是：第1趟歸并排序時，将待排序的檔案R[1..n]看作是n個長度為1的有序子檔案，将這些子檔案兩兩歸并，若n為偶數，則得到
個長度為2的有序子檔案；若n為奇數，則最後一個子檔案輪空(不
參與歸并)。故本趟歸并完成後，前
個有序子檔案長度為2，但最
後一個子檔案長度仍為1；第2趟歸并則是将第1趟歸并所得到的
個有
序的子檔案兩兩歸并，如此反複，直到最後得到一個長度為n的有序檔案為止。
上述的每次歸并操作，均是将兩個有序的子檔案合并成一個有序的子檔案，故稱其為"二路歸并排序"。類似地有k(k>2)路歸并排序。
（2） 二路歸并排序的全過程 (略)
（3） 一趟歸并算法
分析：
在某趟歸并中，設各子檔案長度為length(最後一個子檔案的長度可能小于length)，則歸并前R[1..n]中共有
個有序的子檔案：R
[1..length]，R[length+1..2length]，…，
。
注意：
調用歸并操作将相鄰的一對子檔案進行歸并時，必須對子檔案的個數可能是奇數、以及最後一個子檔案的長度小于length這兩種特殊情況進行特殊處理：
① 若子檔案個數為奇數，則最後一個子檔案無須和其它子檔案歸并(即本趟輪空)；
② 若子檔案個數為偶數，則要注意最後一對子檔案中後一子檔案的區間上界是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、自頂向下的方法
采用分治法進行自頂向下的算法設計，形式更為簡潔。
（1）分治法的三個步驟
設歸并排序的目前區間是R[low..high]，分治法的三個步驟是：
①分解：将目前區間一分為二，即求分裂點
②求解：遞歸地對兩個子區間R[low..mid]和R[mid+1..high]進行歸并排序；
③組合：将已排序的兩個子區間R[low..mid]和R[mid+1..high]歸并為一個有序的區間R[low..high]。
遞歸的終結條件：子區間長度為1（一個記錄自然有序）。
（2）具體算法
void MergeSortDC(SeqList R，int low，int high)
{//用分治法對R[low..high]進行二路歸并排序
int mid；
if(low<high){//區間長度大于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)； //組合，将兩個有序區歸并為一個有序區
}
}//MergeSortDC
（3）算法MergeSortDC的執行過程 (略)
算法MergeSortDC的執行過程如下圖所示歸樹。
二、算法分析
1、穩定性
歸并排序是一種穩定的排序。
2、存儲結構要求
可用順序存儲結構。也易于在連結清單上實作。
3、時間複雜度
對長度為n的檔案，需進行
趟二路歸并，每趟歸并的時間為O(n)，故其時間複雜度無論是在最好情況下還是在最壞情況下均是O(nlgn)。
4、空間複雜度
需要一個輔助向量來暫存兩有序子檔案歸并的結果，故其輔助空間複雜度為O(n)，顯然它不是就地排序。
注意：
若用單連結清單做存儲結構，很容易給出就地的歸并排序