一、歸并排序
歸并過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則将第一個有序表中的元素a[i]複制到r[k]中，并令i和k分别加上1；否則将第二個有序表中的元素a[j]複制到r[k]中，并令j和k分别加上1，如此循環下去，直到其中一個有序表取完，然後再将另一個有序表中剩餘的元素複制到r中從下标k到下标t的單元。歸并排序的算法我們通常用遞歸實作，先把待排序區間[s,t]以中點二分，接着把左邊子區間排序，再把右邊子區間排序，最後把左區間和右區間用一次歸并操作合并成有序的區間[s,t]。
二、歸并操作
三、兩路歸并算法
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、歸并算法
四、歸并排序
歸并排序有兩種實作方法：自底向上和自頂向下。下面說說自頂向下的方法
（1）分治法的三個步驟
設歸并排序的目前區間是R[low..high]，分治法的三個步驟是：
①分解：将目前區間一分為二，即求分裂點
②求解：遞歸地對兩個子區間R[low..mid]和R[mid+1..high]進行歸并排序；
③組合：将已排序的兩個子區間R[low..mid]和R[mid+1..high]歸并為一個有序的區間R[low..high]。
遞歸的終結條件：子區間長度為1（一個記錄自然有序）。
（2）具體算法
（3）算法MergeSortDC的執行過程
算法MergeSortDC的執行過程如下圖所示的遞歸樹。
五、算法分析
1、穩定性
歸并排序是一種穩定的排序。
2、存儲結構要求
可用順序存儲結構。也易于在連結清單上實作。
3、時間複雜度
對長度為n的檔案，需進行 趟二路歸并，每趟歸并的時間為O(n)，故其時間複雜度無論是在最好情況下還是在最壞情況下均是O(nlgn)。
4、空間複雜度
需要一個輔助向量來暫存兩有序子檔案歸并的結果，故其輔助空間複雜度為O(n)，顯然它不是就地排序。
注意：
若用單連結清單做存儲結構，很容易給出就地的歸并排序。
5、比較操作的次數介于(nlogn) / 2和nlogn - n + 1。
6、指派操作的次數是(2nlogn)。歸并算法的空間複雜度為：0 (n)
7、歸并排序比較占用記憶體，但卻是一種效率高且穩定的算法。
六、代碼實作
七、運作結果
==================================================================================================
作者：歐陽鵬 歡迎轉載，與人分享是進步的源泉！