歸併排序法（Merge Sort，以下簡稱MS）是分治法思想運用的一個典範。其主要算法操作可以分為以下步驟：
Step 1：將n個元素分成兩個含n/2元素的子序列
Step 2：用MS將兩個子序列遞歸排序（最後可以將整個原序列分解成n個子序列）
Step 3：合併兩個已排序好的序列
易知，MS的關鍵在於Merge過程。對於這一過程的理解，算法導論中給出了一個形象的模型。
即假設桌面上有兩堆已排序好的的牌，且每一堆都正面朝下放置。然後我們分別從兩堆牌中選取頂上的一張牌（選取之後，堆頂端又會露出新的頂牌），選取較小的一張，放入輸出堆，另一張放回。
重複這一步驟，最後直到一堆牌為空。由於兩堆牌都是已排序，所以可知，只要將剩下的那堆牌蓋到輸出堆即完成整個排序過程。
基本介紹
- 中文名：歸併排序法
- 外文名：Merge Sort
- 解釋：分治法思想運用
- 地位：分治法思想運用的一個典範
歸併排序法簡介,歸併排序法小插曲,
歸併排序法簡介
歸併排序法（Merge Sort，以下簡稱MS）是分治法思想運用的一個典範。其主要算法操作可以分為以下步驟：
Step 1：將n個元素分成兩個含n/2元素的子序列
Step 2：用MS將兩個子序列遞歸排序（最後可以將整個原序列分解成n個子序列）
Step 3：合併兩個已排序好的序列
易知，MS的關鍵在於Merge過程。對於這一過程的理解，算法導論中給出了一個形象的模型。
即假設桌面上有兩堆已排序好的的牌，且每一堆都正面朝下放置。然後我們分別從兩堆牌中選取頂上的一張牌（選取之後，堆頂端又會露出新的頂牌），選取較小的一張，放入輸出堆，另一張放回。
重複這一步驟，最後直到一堆牌為空。由於兩堆牌都是已排序，所以可知，只要將剩下的那堆牌蓋到輸出堆即完成整個排序過程。
歸併排序法小插曲
算法導論為了簡化偽代碼，在此處用了兩張值為∞的哨兵牌。這樣，除非兩堆都露出哨兵牌，否則所取的兩張牌中必有最小值。這一構想避免了檢查每一個堆是否是空的，但是由於無法在程式中表示哨兵牌（或許可以，只是我不知道罷了），我們只能在實際算法中放棄這一構想。
對於A=<5，2，4，7，1，3，2，6>數組，MS的大致操作流程如下圖：
[5] [2] [4] [7] [1] [3] [2] [6] \ / \ / \ / \ / [2 5] [4 7] [1 3] [2 6] \ / \ / [2 4 5 7] [1 2 3 6] \ / [1 2 2 3 4 5 6 7]
在遞歸的合併過程中，我們需要動態的創建一個快取區，作為上面較小牌的輸出堆。一次合併完畢之後，用快取區的數據覆蓋原始相應數組的數據。
於是乎，我們可以上面的思路，寫出下面的相應代碼（注意邊界成立的條件）
/*
輸 入: a(int[]) - 數組地址
nLeft(int) - 左端下標
nRight(int) - 右端下標
輸 出: -
功 能: 歸併排序
*/
void CSort::MergeSort(int a[], int nLeft, int nRight)
{
if (nLeft < nRight)
{
// 剛開始的時候寫了(nLeft + nRight) >> 1
// 結果導致無限遞歸- -,直接報Stack overflow
int nMid = (nLeft + nRight) >> 1;
// 遞歸分組
MergeSort(a, nLeft, nMid);
MergeSort(a, nMid + 1, nRight);
// 合併
Merge(a, nLeft, nMid + 1, nRight);
}
}
/*
輸 入: a(int[]) - 數組地址
nLeft(int) - 左段數據數組的首下標
nMid(int) - 右段數據數組的首下標
nRight(int) - 右段數據數組的尾下標
輸 出: -
功 能: 合併兩段數據
*/
void CSort::Merge(int a[], int nLeft, int nMid, int nRight)
{
// 設定兩個游標
int nLVer = nLeft;
int nMVer = nMid;
int nLen = nRight - nLeft + 1;
// 創建快取區,用以保存排序完整的數據
int* pArr = new int [nLen];
int* pVernier = pArr;
// 依次從兩堆數據堆中彈出一個數據
// 將較小者置入快取區
// 這裡注意下nMid表示的意義,理解下取等號的理由
while (nLVer < nMid && nMVer <= nRight)
{
if (a[nLVer] <= a[nMVer])
{
// 很多人都說這么寫代碼純粹裝B- -
// 我承認可讀性很差,但是方便....
*pVernier++ = a[nLVer++];
}
else
{
*pVernier++ = a[nMVer++];
}
}
// 找到不為空的數據堆,將其貼上到快取區後
// 此時pVernier剛好指向快取區尾數據向右
// 偏移一個單位的位置
while (nLVer < nMid)
{
*pVernier++ = a[nLVer++];
}
while (nMVer <= nRight)
{
*pVernier++ = a[nMVer++];
}
// 將快取區數據複製回原數組
for (int i = nLeft, k = 0; i <= nRight;)
{
a[i++] = pArr[k++];
}
// 釋放快取資源
delete [] pArr;
}
