可以運用分而治之方法來解決排序問題，該問題是將n個元素排成非遞減順序。分而治之方法通常用以下的步驟來進行排序算法：若n 為1，算法終止；否則，將這一元素集合分割成兩個或更多個子集合，對每一個子集合分別排序，然後將排好序的子集合歸並為一個集合。
假設僅將n個元素的集合分成兩個子集合。現在需要確定如何進行子集合的劃分。一種可能性就是把前面n- 1個元素放到第一個子集中（稱為A），最後一個元素放到第二個子集裡（稱為B）。按照這種方式對A遞歸地進行排序。由於B僅含一個元素，所以它已經排序完畢，在A排完序後，只需要用程序2 - 1 0中的函數i n s e r t將A和B合並起來。把這種排序算法與I n s e r t i o n S o r t（見程序2 - 1 5）進行比較，可以發現這種排序算法實際上就是插入排序的遞歸算法。該算法的復雜性為O (n 2 )。把n個元素劃分成兩個子集合的另一種方法是將含有最大值的元素放入B，剩下的放入A中。然後A被遞歸排序。為了合並排序後的A和B，只需要將B添加到A中即可。假如用函數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）的遞歸算法。這兩種遞歸排序算法的復雜性均為(n2 )。若一旦發現A已經被排好序就終止對A進行遞歸分割，則算法的復雜性為O(n2 )（見例2 - 1 6和2 - 1 7）。
上述分割方案將n個元素分成兩個極不平衡的集合A和B。A有n- 1個元素，而B僅含一個元素。下面來看一看采用平衡分割法會發生什麼情況： A集合中含有n/k個元素，B中包含其余的元素。遞歸地使用分而治之方法對A和B進行排序。然後采用一個被稱之為歸並（ 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 ]將被分別獨立地排序。結果分別為[ 3 , 4 , 6 , 1 0 ]和[ 2 , 5 , 7 , 8 ]。從兩個序列的頭部開始歸並這兩個已排序的序列。元素2比3更小，被移到結果序列；3與5進行比較，3被移入結果序列；4與5比較，4被放入結果序列；5和6比較，.。如果選擇k= 4，則序列[ 1 0 , 4 ]和[ 6 , 3 , 8 , 2 , 5 , 7 ]將被排序。排序結果分別為[ 4 , 1 0 ]和[ 2 , 3 , 5 , 6 , 7 , 8 ]。當這兩個排好序的序列被歸並後，即可得所需要的排序序列。
圖2 - 6給出了分而治之排序算法的偽代碼。算法中子集合的數目為2，A中含有n/k個元素。
template
void sort( T E, int n)
{ / /對E中的n個元素進行排序，k為全局變量
if (n >= k) {
i = n/k;
j = n-i;
令A 包含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 進行排序
}
圖14-6 分而治之排序算法的偽代碼
從對歸並過程的簡略描述中，可以明顯地看出歸並n個元素所需要的時間為O (n)。設t (n)為分而治之排序算法（如圖1 4 - 6所示）在最壞情況下所需花費的時間，則有以下遞推公式：
其中c 和d 為常數。當n / k≈n-n / k 時，t (n)的值最小。因此當k= 2時，也就是說，當兩個子集合所包含的元素個數近似相等時，t (n) 最小，即當所劃分的子集合大小接近時，分而治之算法通常具有最佳性能。
可以用迭代方法來計算這一遞推方式，結果為t(n)= (nl o gn)。雖然這個結果是在n為2的冪時得到的，但對於所有的n，這一結果也是有效的，因為t(n) 是n的非遞減函數。t(n) =(nl o gn) 給出了歸並排序的最好和最壞情況下的復雜性。由於最好和最壞情況下的復雜性是一樣的，因此歸並排序的平均復雜性為t (n)= (nl o gn)。
圖2 - 6中k= 2的排序方法被稱為歸並排序（ m e rge sort ），或更精確地說是二路歸並排序（two-way merge sort）。下面根據圖1 4 - 6中k= 2的情況（歸並排序）來編寫對n個元素進行排序的C + +函數。一種最簡單的方法就是將元素存儲在鏈表中（即作為類c h a i n的成員（程序3 -8））。在這種情況下，通過移到第n/ 2個節點並打斷此鏈，可將E分成兩個大致相等的鏈表。
歸並過程應能將兩個已排序的鏈表歸並在一起。如果希望把所得到C + +程序與堆排序和插入排序進行性能比較，那麼就不能使用鏈表來實現歸並排序，因為後兩種排序方法中都沒有使用鏈表。為了能與前面討論過的排序函數作比較，歸並排序函數必須用一個數組a來存儲元素集合E，並在a 中返回排序後的元素序列。為此按照下述過程來對圖1 4 - 6的偽代碼進行細化：當集合E被化分成兩個子集合時，可以不必把兩個子集合的元素分別復制到A和B中，只需簡單地在集合E中保持兩個子集合的左右邊界即可。接下來對a 中的初始序列進行排序，並將所得到的排序序列歸並到一個新數組b中，最後將它們復制到a 中。圖1 4 - 6的改進版見圖1 4 - 7。
template
M e rgeSort( T a[], int left, int right)
{ / /對a [ l e f t : r i g h t ]中的元素進行排序
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); //結果放回a
}
}
圖14-7 分而治之排序算法的改進
可以從很多方面來改進圖1 4 - 7的性能，例如，可以容易地消除遞歸。如果仔細地檢查圖1 4 - 7中的程序，就會發現其中的遞歸只是簡單地重復分割元素序列，直到序列的長度變成1為止。當序列的長度變為1時即可進行歸並操作，這個過程可以用n 為2的冪來很好地描述。長度為1的序列被歸並為長度為2的有序序列；長度為2的序列接著被歸並為長度為4的有序序列；這個過程不斷地重復直到歸並為長度為n的序列。圖1 4 - 8給出n= 8時的歸並（和復制）過程，方括號表示一個已排序序列的首和尾。
初始序列[8] [4] [5] [6] [2] [1] [7] [3]
歸並到b [4 8] [5 6] [1 2] [3 7]
復制到a [4 8] [5 6] [1 2] [3 7]
歸並到b [4 5 6 8] [1 2 3 7]
復制到a [4 5 6 8] [1 2 3 7]
歸並到b [1 2 3 4 5 6 7 8]
復制到a [1 2 3 4 5 6 7 8]
圖14-8歸並排序的例子
另一種二路歸並排序算法是這樣的：首先將每兩個相鄰的大小為1的子序列歸並，然後對上一次歸並所得到的大小為2的子序列進行相鄰歸並，如此反復，直至最後歸並到一個序列，歸並過程完成。通過輪流地將元素從a歸並到b並從b歸並到a，可以虛擬地消除復制過程。二路歸並排序算法見程序1 4 - 3。
程序14-3 二路歸並排序
template
void MergeSort(T a[], int n)
{// 使用歸並排序算法對a[0:n-1] 進行排序
T *b = new T [n];
int s = 1; // 段的大小
while (s < n) {
MergePass(a, b, s, n); // 從a歸並到b
s += s;
MergePass(b, a, s, n); // 從b歸並到a
s += s;
}
}
為了完成排序代碼，首先需要完成函數M e rg e P a s s。函數M e rg e P a s s（見程序1 4 - 4）僅用來確定欲歸並子序列的左端和右端，實際的歸並工作由函數M e rg e (見程序1 4 - 5 )來完成。函數M e rg e要求針對類型T定義一個操作符< =。如果需要排序的數據類型是用戶自定義類型，則必須重載操作符< =。這種設計方法允許我們按元素的任一個域進行排序。重載操作符< =的目的是用來比較需要排序的域。
程序14-4 MergePass函數
template
void MergePass(T x[], T y[], int s, int n)
{//歸並大小為s的相鄰段
int i = 0;
while (i <= n - 2 * s) {
//歸並兩個大小為s的相鄰段
Merge(x, y, i, i+s-1, i+2*s-1);
i = i + 2 * s;
}
// 剩下不足2個元素
if (i + s < n) Merge(x, y, i, i+s-1, n-1);
else for (int j = i; j <= n-1; j++)
// 把最後一段復制到y
y[j] = x[j];
}
程序14-5 Merge函數
template
void Merge(T c[], T d[], int l, int m, int r)
{// 把c[l:m]] 和c[m:r]歸並到d [ l : r ] .
int i = l, // 第一段的游標
j = m+1, // 第二段的游標
k = l; // 結果的游標
/ /只要在段中存在i和j，則不斷進行歸並
while ((i <= m) && (j <= r))
if (c[i] <= c[j]) d[k++] = c[i++];
else d[k++] = c[j++];
// 考慮余下的部分
if (i > m) for (int q = j; q <= r; q++)
d[k++] = c[q];
else for (int q = i; q <= m; q++)
d[k++] = c[q];
}
自然歸並排序（natural merge sort）是基本歸並排序（見程序1 4 - 3）的一種變化。它首先對輸入序列中已經存在的有序子序列進行歸並。例如，元素序列[ 4，8，3，7，1，5，6，2 ]中包含有序的子序列[ 4，8 ]，[ 3，7 ]，[ 1，5，6 ]和[ 2 ]，這些子序列是按從左至右的順序對元素表進行掃描而產生的，若位置i的元素比位置i+ 1的元素大，則從位置i 進行分割。對於上面這個元素序列，可找到四個子序列，子序列1和子序列2歸並可得[ 3 , 4 , 7 , 8 ]，子序列3和子序列4歸並可得[ 1 , 2 , 5 , 6 ]，最後，歸並這兩個子序列得到[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。因此，對於上述元素序列，僅僅使用了兩趟歸並，而程序1 4 - 3從大小為1的子序列開始，需使用三趟歸並。作為一個極端的例子，假設輸入的元素序列已經排好序並有n個元素，自然歸並排序法將准確地識別該序列不必進行歸並排序，但程序1 4 - 3仍需要進行[ l o g2 n]趟歸並。因此自然歸並排序將在(n)的時間內完成排序。而程序1 4 - 3將花費(n l o gn)的時間。
