二路合并排序算法，使用分治策略,時間復(fù)雜度O(nlog2n),
需要和待排記錄等數(shù)量的輔助空間，是一種穩(wěn)定的排序算法

可以運(yùn)用分而治之方法來解決排序問題，該問題是將n 個元素排成非遞減順序。分而治之方法通常用以下的步驟來進(jìn)行排序算法：若n 為1，算法終止；否則，將這一元素集合分割成兩個或更多個子集合，對每一個子集合分別排序，然后將排好序的子集合歸并為一個集合。 

假設(shè)僅將n 個元素的集合分成兩個子集合。現(xiàn)在需要確定如何進(jìn)行子集合的劃分。一種可能性就是把前面n- 1個元素放到第一個子集中（稱為A），最后一個元素放到第二個子集里（稱為B）。按照這種方式對A遞歸地進(jìn)行排序。由于B僅含一個元素，所以它已經(jīng)排序完畢，在A排完序后，只需要用程序2 - 1 0中的函數(shù)i n s e r t將A和B合并起來。把這種排序算法與I n s e r t i o n S o r t（見程序2 - 1 5）進(jìn)行比較，可以發(fā)現(xiàn)這種排序算法實際上就是插入排序的遞歸算法。該算法的復(fù)雜性為O (n 2 )。把n 個元素劃分成兩個子集合的另一種方法是將含有最大值的元素放入B，剩下的放入A中。然后A被遞歸排序。為了合并排序后的A和B，只需要將B添加到A中即可。假如用函數(shù)M a x（見程序1 - 3 1）來找出最大元素，這種排序算法實際上就是S e l e c t i o n S o r t（見程序2 - 7）的遞歸算法。 

假如用冒泡過程（見程序2 - 8）來尋找最大元素并把它移到最右邊的位置，這種排序算法就是B u b b l e S o r t（見程序2 - 9）的遞歸算法。這兩種遞歸排序算法的復(fù)雜性均為(n2 )。若一旦發(fā)現(xiàn)A已經(jīng)被排好序就終止對A進(jìn)行遞歸分割，則算法的復(fù)雜性為O(n2 )（見例2 - 1 6和2 - 1 7）。 

上述分割方案將n 個元素分成兩個極不平衡的集合A和B。A有n- 1個元素，而B僅含一個元素。下面來看一看采用平衡分割法會發(fā)生什么情況： A集合中含有n/k 個元素，B中包含其余的元素。遞歸地使用分而治之方法對A和B進(jìn)行排序。然后采用一個被稱之為歸并（ m e rg e）的過程，將已排好序的A和B合并成一個集合。 

例2-5 考慮8個元素，值分別為[ 1 0，4，6，3，8，2，5，7 ]。如果選定k = 2，則[ 1 0 , 4 , 6 , 3 ]和[ 8 , 2 , 5 , 7 ]將被分別獨(dú)立地排序。結(jié)果分別為[ 3 , 4 , 6 , 1 0 ]和[ 2 , 5 , 7 , 8 ]。從兩個序列的頭部開始?xì)w并這兩個已排序的序列。元素2比3更小，被移到結(jié)果序列；3與5進(jìn)行比較，3被移入結(jié)果序列；4與5比較，4被放入結(jié)果序列；5和6比較，.。如果選擇k= 4，則序列[ 1 0 , 4 ]和[ 6 , 3 , 8 , 2 , 5 , 7 ]將被排序。排序結(jié)果分別為[ 4 , 1 0 ]和[ 2 , 3 , 5 , 6 , 7 , 8 ]。當(dāng)這兩個排好序的序列被歸并后，即可得所需要的排序序列。 

圖2 - 6給出了分而治之排序算法的偽代碼。算法中子集合的數(shù)目為2，A中含有n/k個元素。 

template 

void sort( T E, int n) 

{ / /對E中的n 個元素進(jìn)行排序， k為全局變量 

if (n >= k) { 

i = n/k; 

j = n-i; 

令A(yù) 包含E中的前i 個元素 

令B 包含E中余下的j 個元素 

s o r t ( A , i ) ; 

s o r t ( B , j ) ; 

m e rge(A,B,E,i,j,); //把A 和B 合并到E 

} 

else 使用插入排序算法對E 進(jìn)行排序 

} 

圖14-6 分而治之排序算法的偽代碼 



從對歸并過程的簡略描述中，可以明顯地看出歸并n個元素所需要的時間為O (n)。設(shè)t (n)為分而治之排序算法（如圖1 4 - 6所示）在最壞情況下所需花費(fèi)的時間，則有以下遞推公式： 

其中c 和d 為常數(shù)。當(dāng)n / k≈n-n / k 時，t (n) 的值最小。因此當(dāng)k= 2時，也就是說，當(dāng)兩個子集合所包含的元素個數(shù)近似相等時， t (n) 最小，即當(dāng)所劃分的子集合大小接近時，分而治之算法通常具有最佳性能。 

可以用迭代方法來計算這一遞推方式，結(jié)果為t(n)= (nl o gn)。雖然這個結(jié)果是在n為2的冪時得到的，但對于所有的n，這一結(jié)果也是有效的，因為t(n) 是n 的非遞減函數(shù)。t(n) =(nl o gn) 給出了歸并排序的最好和最壞情況下的復(fù)雜性。由于最好和最壞情況下的復(fù)雜性是一樣的，因此歸并排序的平均復(fù)雜性為t (n)= (nl o gn)。 

圖2 - 6中k= 2的排序方法被稱為歸并排序（ m e rge sort ），或更精確地說是二路歸并排序（two-way merge sort）。下面根據(jù)圖1 4 - 6中k= 2的情況（歸并排序）來編寫對n 個元素進(jìn)行排序的C + +函數(shù)。一種最簡單的方法就是將元素存儲在鏈表中（即作為類c h a i n的成員（程序3 -8））。在這種情況下，通過移到第n/ 2個節(jié)點并打斷此鏈，可將E分成兩個大致相等的鏈表。 

歸并過程應(yīng)能將兩個已排序的鏈表歸并在一起。如果希望把所得到C + +程序與堆排序和插入排序進(jìn)行性能比較，那么就不能使用鏈表來實現(xiàn)歸并排序，因為后兩種排序方法中都沒有使用鏈表。為了能與前面討論過的排序函數(shù)作比較，歸并排序函數(shù)必須用一個數(shù)組a來存儲元素集合E，并在a 中返回排序后的元素序列。為此按照下述過程來對圖1 4 - 6的偽代碼進(jìn)行細(xì)化：當(dāng)集合E被化分成兩個子集合時，可以不必把兩個子集合的元素分別復(fù)制到A和B中，只需簡單地在集合E中保持兩個子集合的左右邊界即可。接下來對a 中的初始序列進(jìn)行排序，并將所得到的排序序列歸并到一個新數(shù)組b中，最后將它們復(fù)制到a 中。圖1 4 - 6的改進(jìn)版見圖1 4 - 7。 



template 

M e rgeSort( T a[], int left, int right) 

{ / /對a [ l e f t : r i g h t ]中的元素進(jìn)行排序 

if (left < right) {//至少兩個元素 

int i = (left + right)/2; //中心位置 

M e rgeSort(a, left, i); 

M e rgeSort(a, i+1, right); 

M e rge(a, b, left, i, right); //從a 合并到b 

Copy(b, a, left, right); //結(jié)果放回a 

} 

} 

圖14-7 分而治之排序算法的改進(jìn) 



可以從很多方面來改進(jìn)圖1 4 - 7的性能，例如，可以容易地消除遞歸。如果仔細(xì)地檢查圖1 4 - 7中的程序，就會發(fā)現(xiàn)其中的遞歸只是簡單地重復(fù)分割元素序列，直到序列的長度變成1為止。當(dāng)序列的長度變?yōu)?時即可進(jìn)行歸并操作，這個過程可以用n 為2的冪來很好地描述。長度為1的序列被歸并為長度為2的有序序列；長度為2的序列接著被歸并為長度為4的有序序列；這個過程不斷地重復(fù)直到歸并為長度為n 的序列。圖1 4 - 8給出n= 8時的歸并（和復(fù)制）過程，方括號表示一個已排序序列的首和尾。 



初始序列[8] [4] [5] [6] [2] [1] [7] [3] 

歸并到b [4 8] [5 6] [1 2] [3 7]