合并排序（MERGE SORT）是又一類(lèi)不同的排序方法，合并的含義就是將兩個(gè)或兩個(gè)以上的有序數(shù)據(jù)序列合并成一個(gè)新的有序數(shù)據(jù)序列，因此它又叫歸并算法。它的基本思想就是假設(shè)數(shù)組A有N個(gè)元素，那么可以看成數(shù)組A是又N個(gè)有序的子序列組成，每個(gè)子序列的長(zhǎng)度為1，然后再兩兩合并，得到了一個(gè) N/2 個(gè)長(zhǎng)度為2或1的有序子序列，再兩兩合并，如此重復(fù)，值得得到一個(gè)長(zhǎng)度為N的有序數(shù)據(jù)序列為止，這種排序方法稱(chēng)為2—路合并排序。
例如數(shù)組A有7個(gè)數(shù)據(jù)，分別是： 49 38 65 97 76 13 27，那么采用歸并排序算法的操作過(guò)程如圖7所示：
初始值 [49] [38] [65] [97] [76] [13] [27]
看成由長(zhǎng)度為1的7個(gè)子序列組成
第一次合并之后 [38 49] [65 97] [13 76] [27]
看成由長(zhǎng)度為1或2的4個(gè)子序列組成
第二次合并之后 [38 49 65 97] [13 27 76]
看成由長(zhǎng)度為4或3的2個(gè)子序列組成
第三次合并之后 [13 27 38 49 65 76 97]
圖6 歸并排序算法過(guò)程圖
合并算法的核心操作就是將一維數(shù)組中前后相鄰的兩個(gè)兩個(gè)有序序列合并成一個(gè)有序序列。合并算法也可以采用遞歸算法來(lái)實(shí)現(xiàn)，形式上較為簡(jiǎn)單,但實(shí)用性很差。
合并算法的合并次數(shù)是一個(gè)非常重要的量,根據(jù)計(jì)算當(dāng)數(shù)組中有3到4個(gè)元素時(shí),合并次數(shù)是2次,當(dāng)有5到8個(gè)元素時(shí),合并次數(shù)是3次,當(dāng)有9到16個(gè)元素時(shí),合并次數(shù)是4次，按照這一X規(guī)律,當(dāng)有N個(gè)子序列時(shí)可以推斷出合并的次數(shù)是X(2 >=N,符合此條件的最小那個(gè)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;