歸並排序（Merge sort，合並排序）是建立在歸並操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。
一 歸並操作
基本思想
歸並操作(merge)，指的是將兩個已經排序的序列合並成一個序列的操作，歸並排序算法依賴歸並操作。
歸並操作的過程如下：
申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列
設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置
重復步驟3直到某一指針達到序列尾
將另一序列剩下的所有元素直接復制到合並序列尾
歸並操作算法實現（c/c++）
[cpp]
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
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
二 歸並排序
歸並排序是基於歸並操作的排序算法，有多路歸並排序、兩路歸並排序 , 可用於內排序，也可以用於外排序
兩路歸並排序
基本思路
設兩個有序的子文件(相當於輸入堆)放在同一向量中相鄰的位置上：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是動態申請的，因為申請的空間可能很大，故須加入申請空間是否成功的處理。
算法實現
自底向上的方法
（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]，[length+1..2length]，…， 。
注意：
調用歸並操作將相鄰的一對子文件進行歸並時，必須對子文件的個數可能是奇數、以及最後一個子文件的長度小於length這兩種特殊情況進行特殊處理：
① 若子文件個數為奇數，則最後一個子文件無須和其它子文件歸並(即本趟輪空)；
② 若子文件個數為偶數，則要注意最後一對子文件中後一子文件的區間上界是n。
具體實現算法：
[cpp]
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
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）二路歸並排序算法
[cpp] view plaincopyprint?void MergeSort(SeqList R)
{//采用自底向上的方法，對R[1..n]進行二路歸並排序
int length；
for(1ength=1；length<n；length*=2) //做 趟歸並
MergePass(R，length)； //有序段長度≥n時終止
}
void MergeSort(SeqList R)
{//采用自底向上的方法，對R[1..n]進行二路歸並排序
int length；
for(1ength=1；length<n；length*=2) //做 趟歸並
MergePass(R，length)； //有序段長度≥n時終止
}
注意：
自底向上的歸並排序算法雖然效率較高，但可讀性較差。
自頂向下的方法
采用分治法進行自頂向下的算法設計，形式更為簡潔。
（1）分治法的三個步驟
設歸並排序的當前區間是R[low..high]，分治法的三個步驟是：
①分解：將當前區間一分為二，即求分裂點
②求解：遞歸地對兩個子區間R[low..mid]和R[mid+1..high]進行歸並排序；
③組合：將已排序的兩個子區間R[low..mid]和R[mid+1..high]歸並為一個有序的區間R[low..high]。
遞歸的終結條件：子區間長度為1（一個記錄自然有序）。
（2）具體算法
[cpp]
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
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)，顯然它不是就地排序。
