歸并排序算法以O(shè)（nlogn）最壞情形運(yùn)行時(shí)間運(yùn)行，而所使用的比較次數(shù)幾乎是最優(yōu)的。它可以用遞歸的形式實(shí)現(xiàn)，形式簡(jiǎn)潔易懂。但是需要注意的是當(dāng)用遞歸形式時(shí)，如果數(shù)據(jù)較多，則開(kāi)銷很大，實(shí)用性很差，所以我們一般采用非遞歸的形式。我這里兩種形式都給出。
不管是遞歸還是非遞歸，歸并排序算法中基本的操作是合并兩個(gè)已經(jīng)排序的數(shù)組。
遞歸形式：
template <class T>
void MSort(T a[], int left, int right)
{
if (left < right)
{
int center = (left + right) / 2;
MSort(a, left, center);
MSort(a, center+1, right);
Merge(a, left, center, right, right-left+1);
}
}
template <class T>
void MergeSort(T a[], int n)
{
MSort(a, 0, n-1);
}
///////////////////////////////////////////////////////////////////////
非遞歸形式：
算法介紹：先介紹三個(gè)變量beforeLen，afterLen和i的作用：
int beforeLen; //合并前序列的長(zhǎng)度
int afterLen;//合并后序列的長(zhǎng)度，合并后序列的長(zhǎng)度是合并前的兩倍
int i = 0;//開(kāi)始合并時(shí)第一個(gè)序列的起始位置下標(biāo)，每次都是從0開(kāi)始
i，i+beforeLen-1，i+afterLen-1定義被合并的兩個(gè)序列的邊界。
算法的工作過(guò)程如下：
開(kāi)始時(shí)，beforeLen被置為1，i被置為0。外部for循環(huán)的循環(huán)體每執(zhí)行一次，都使beforeLen和afterLen加倍。內(nèi)部的while循環(huán)執(zhí)行序列的合并工作，他的循環(huán)體每執(zhí)行一次，i都向前移動(dòng)afterLen個(gè)位置。當(dāng)n不是afterLen的倍數(shù)時(shí)，如果被合并序列的起始位置i，加上合并后序列的長(zhǎng)度afterLen，超過(guò)輸入數(shù)組的邊界n，就結(jié)束內(nèi)部循環(huán)；此時(shí)如果被合并序列的起始位置i，加上合并前序列的長(zhǎng)度beforeLen，小于輸入數(shù)組的邊界n，還需要執(zhí)行一次合并工作，把最后長(zhǎng)度不足afterLen，但超過(guò)beforeLen的序列合并起來(lái)。這個(gè)工作由算法的語(yǔ)句Merge(a, i, i+beforeLen-1, n-1, n);完成。
template <class T>
void MergeSort(T a[], int n)
{
int beforeLen; //合并前序列的長(zhǎng)度
int afterLen = 1;//合并后序列的長(zhǎng)度
for (beforeLen=1; afterLen<n; beforeLen=afterLen)
{
int i = 0;//開(kāi)始合并時(shí)第一個(gè)序列的起始位置下標(biāo)，每次都是從0開(kāi)始
afterLen = 2 * beforeLen; //合并后序列的長(zhǎng)度是合并前的兩倍
while (i+afterLen < n)
{
Merge(a, i, i+beforeLen-1, i+afterLen-1, afterLen);
i += afterLen;
}
if (i+beforeLen < n)
Merge(a, i, i+beforeLen-1, n-1, n);
}
}
///////////////////////////////////////////////////////////
上面兩種算法都要用到下面的合并函數(shù)。
/*函數(shù)介紹：合并兩個(gè)有序的子數(shù)組
輸入：數(shù)組a[]，下標(biāo)left，center，right，元素個(gè)數(shù)n，a[left]~a[center]及a[center+1]~a[right]已經(jīng)按非遞減順序排序。
輸出：按非遞減順序排序的子數(shù)組a[left]~a[right]。
*/
template <class T>
void Merge(T a[], int left, int center, int right, int n)
{
T *t = new T[n];//存放被排序的元素
int i = left;
int j = center + 1;
int k = 0;
while (i<=center && j<=right)
{
if (a[i] <= a[j])
t[k++] = a[i++];
else
t[k++] = a[j++];
}
if (i == center+1)
{
while (j <= right)
t[k++] = a[j++];
}
else
{
while (i <= center)
t[k++] = a[i++];
}
//把t[]的元素復(fù)制回a[]
for (i=left,k=0; i<=right; i++,k++)
a[i] = t[k];
delete []t;
}