合并排序（MERGE SORT）是又一類不同的排序方法，合并的含義就是將兩個或兩個以上的有序數據序列合并成一個新的有序數據序列，因此它又叫歸并算法。它的基本思想就是假設數組A有N個元素，那么可以看成數組A是又N個有序的子序列組成，每個子序列的長度為1，然后再兩兩合并，得到了一個 N/2 個長度為2或1的有序子序列，再兩兩合并，如此重復，值得得到一個長度為N的有序數據序列為止，這種排序方法稱為2—路合并排序。
例如數組A有7個數據，分別是： 49 38 65 97 76 13 27，那么采用歸并排序算法的操作過程如圖7所示：
初始值 [49] [38] [65] [97] [76] [13] [27]
看成由長度為1的7個子序列組成
第一次合并之后 [38 49] [65 97] [13 76] [27]
看成由長度為1或2的4個子序列組成
第二次合并之后 [38 49 65 97] [13 27 76]
看成由長度為4或3的2個子序列組成
第三次合并之后 [13 27 38 49 65 76 97]
圖6 歸并排序算法過程圖
合并算法的核心操作就是將一維數組中前后相鄰的兩個兩個有序序列合并成一個有序序列。合并算法也可以采用遞歸算法來實現，形式上較為簡單,但實用性很差。
合并算法的合并次數是一個非常重要的量,根據計算當數組中有3到4個元素時,合并次數是2次,當有5到8個元素時,合并次數是3次,當有9到16個元素時,合并次數是4次，按照這一X規律,當有N個子序列時可以推斷出合并的次數是X(2 >=N,符合此條件的最小那個X)。
源程序：
program?hebing;?
const?
??n=10;?
var?
??a:array[1..n]?of?integer;?
??i:integer;?
?
?procedure?init;?
?var?
????i:integer;?
?begin?
?for?i:=1?to?n?do?read(a[i]);?
?readln;?
?end;?
?
?procedure?merge(low,mid,high:integer);?
?var?
?h,i,j,k:integer;?
?b:array[1..n]?of?integer;?
?begin?
?h:=low;?i:=low;?j:=mid+1;?
?while?(h<=mid)?and?(j<=high)?do?begin?
?if?(a[h]<=a[j])?then?begin
???b[i]:=a[h];?h:=h+1;?
?end?else?begin?
?b[i]:=a[j];?j:=j+1;?
?end;?
?i:=i+1;?
?end;?
?
?if?h>mid?then?
?for?k:=j?to?high?do?begin?
???b[i]:=a[k];?i:=i+1;
?end?else?
?for?k:=h?to?mid?do?begin?
?b[i]:=a[k];?i:=i+1;?
?end;?
?
?for?k:=low?to?high?do?a[k]:=b[k];
?end;?
?
?procedure?mergesort(low,high:integer);?
?var?
?mid:integer;?
?begin?
?if?low<high?then?begin?
?mid:=(low+high)?div?2;?
?mergesort(low,mid);?
?mergesort(mid+1,high);?
?merge(low,mid,high);?
?end;?
?end;