一、兩路歸併算法
1、算法基本思路
設有兩個有序（升序）序列存儲在同一數組中相鄰的位置上，不妨設為A[l..m]，A[m+1..h]，將它們歸併為一個有序數列，並存儲在A[l..h]。
為了減少數據移動次數，不妨採用一個臨時工作數組C，將中間排序結果暫時保存在C數組中，等歸併結束後，再將C數組值複製給A。
歸併過程中，設定p1，p2和p3三個指針，其初值分別指向三個有序區的起始位置。歸併時依次比較A[p1]和A[p2]的關鍵字，取關鍵字較小的記錄複製到C[p3]中，然後將被複製記錄的指針p1或p2加1，以及指向複製位置的指針p3加1。
重複這一過程直至有一個已複製完畢，此時將另一序列中剩餘數據依次複製到C中即可。
2）（1）自底向上的基本思想
自底向上的基本思想是：第1趟歸併排序時，將數列A[1..n]看作是n個長度為1的有序序列，將這些序列兩兩歸併，若n為偶數，則得到[n/2]個長度為2的有序序列；若n為奇數，則最後一個子序列不參與歸併。第2趟歸併則是將第1趟歸併所得到的有序序列兩兩歸併。如此反覆，直到最後得到一個長度為n的有序檔案為止。
上述的每次歸併操作，均是將兩個有序序列合併成一個有序序列，故稱其為“二路歸併排序”。
