本文主要描述了歸并排序的兩種實作方式，遞歸方式和非遞歸方式，以及二者的優缺點比較。下面首先介紹一下歸并排序的原理。
一、了解歸并排序
歸并排序的本質：通過兩兩合并排序再合并，最終獲得了一個有序的數組。通過在紙上示範，就會發現它其實是一棵倒置的完全二叉樹。
原理：假設初始序列含有n個記錄，則可以看成是n個有序的子序列，每個子序列的長度為1，然後兩兩歸并，得到n/2個長度為2或1的有序子序列；再兩兩歸并，…，如此重複，直到得到一個長度為n的有序序列為止，這種排序方法稱為2路歸并排序。也是分治法的典型應用。下面來張圖，直覺的感受一下：
二、遞歸方式實作
1.實作過程
（1）拆分：先将待排序列拆分成單個元素。
（2）合并：拆分之後，再按照有序的進行合并。
具體代碼如下：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 歸并排序
{
class MergeSortTest
{
private static MergeSortTest _instance;
public static MergeSortTest Instance {
get {
if (_instance == null)
{
_instance = new MergeSortTest();
}
return _instance;
}
}
//遞歸實作
public void MergeSort(int[] datas)
{
//拆分時遞歸 調用與合并
MSort(datas,datas,,datas.Length-);
}
/// <summary>
/// 将SR[s..t]歸并排序為TR1[s..t]
/// </summary>
/// <param name="SR">歸并前原始序列</param>
/// <param name="TR1">每次歸并後的結果</param>
/// <param name="s">SR歸并開始的索引</param>
/// <param name="t">SR歸并結束的索引</param>
private void MSort(int[] SR, int[] TR1, int s, int t)
{
int m;
int[] TR2 = new int[SR.Length]; //用于每次遞歸臨時存放待排序的子序列
//遞歸終止條件
if (s == t)
{
TR1[s] = SR[s];
}
else
{
m = (s + t) / ;
//遞歸拆分，并把子序列儲存在TR2中
MSort(SR,TR2, s,m);//左拆分
MSort(SR,TR2,m+,t);//右拆分
//遞歸合并排序
//将TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]
Merge(TR2,TR1,s,m,t); //TR2為有序的，TR1為空
}
}
/// <summary>
/// 将有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]
/// </summary>
/// <param name="SR">上述裡面的TR2</param>
/// <param name="TR">儲存排序的結果</param>
/// <param name="i">TR2序列的起始位置</param>
/// <param name="m">TR2序列的中間位置</param>
/// <param name="n">TR2序列的結束位置</param>
private void Merge(int[] SR, int[] TR, int i, int m, int n)
{
int j, k, l; //i指向SR的[i..m],j指向SR的[m+1..n],k指向TR
for (j = m + , k = i; i <= m && j <= n;k++)
{
if (SR[i] < SR[j])
{
TR[k] = SR[i++];
}
else
{
TR[k] = SR[j++];
}
}
if (i <= m)
{
//将剩餘的SR[i..m]複制到TR
for (l = ; l <= m - i; l++)
{
TR[k + l] = SR[i+l];
}
}
if (j <= n)
{
//将剩餘的SR[j..m]複制到TR
for (l = ; l <= n - j; l++)
{
TR[k + l] = SR[j+l];
}
}
}
}
}
2.遞歸方式的特點
一趟歸并需要将SR[0]~SR[n]中相鄰的長度為h的有序序列進行兩兩歸并，并将結果放到TR1[0]~TR1[n]中，這需要将待排序列序列中的所有記錄掃描一遍，是以耗費O（n）時間，而由完全二叉樹的深度可知，這個歸并排序的需要進行log2(n)次，是以總的時間複雜度為O（nlogn），而且這是歸并排序算法中最好、最壞、平均的時間性能。由于歸并排序的過程中需要與原始記錄序列同樣數量的存儲空間存放歸并結果以及遞歸時深度為log2（n）的棧空間，是以空間複雜度為O（n+logn）。由于是挨個比較，是以歸并排序是一種穩定的排序算法，比較占用記憶體，但效率高且穩定的算法。
三、非遞歸方式實作
1.實作過程
非遞歸方式就少了拆分過程，直接按照2，4，…，2n方式進行歸并，歸并的方式采用循環的來實作。具體實作方式如下：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 歸并排序
{
class MergeSortTest
{
private static MergeSortTest _instance;
public static MergeSortTest Instance {
get {
if (_instance == null)
{
_instance = new MergeSortTest();
}
return _instance;
}
}
//非遞歸實作
public void MergeSort2(int[] datas)
{
int[] TR = new int[datas.Length];
int k = ; //歸并增量
while (k < datas.Length)
{
//datas與TR 來回歸并
MergePass(datas, TR, k, datas.Length - );
k = * k;
MergePass(TR, datas, k, datas.Length - );
k = * k;
}
}
//将SR[]中相鄰長度為s的子序列兩兩歸并到TR[]，s歸并長度增量，n待排序列最後元素的下标
public void MergePass(int[] SR, int[] TR, int s, int n)
{
int i = , j;
//兩兩歸并
while (i <= n - * s + )
{
Merge(SR, TR, i, i + s - , i + * s - );
i = i + * s;
}
//歸并最後兩個子序列
if (i < n - s + )
{
Merge(SR, TR, i, i + s - , n);
}
//若最後隻剩單個子序列
else
{
for (j = i; j <= n; j++)
{
TR[j] = SR[j];
}
}
}
/// <summary>
/// 将有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]
/// </summary>
/// <param name="SR">上述裡面的TR2</param>
/// <param name="TR">儲存排序的結果</param>
/// <param name="i">TR2序列的起始位置</param>
/// <param name="m">TR2序列的中間位置</param>
/// <param name="n">TR2序列的結束位置</param>
private void Merge(int[] SR, int[] TR, int i, int m, int n)
{
int j, k, l; //i指向SR的[i..m],j指向SR的[m+1..n],k指向TR
for (j = m + , k = i; i <= m && j <= n;k++)
{
if (SR[i] < SR[j])
{
TR[k] = SR[i++];
}
else
{
TR[k] = SR[j++];
}
}
if (i <= m)
{
//将剩餘的SR[i..m]複制到TR
for (l = ; l <= m - i; l++)
{
TR[k + l] = SR[i+l];
}
}
if (j <= n)
{
//将剩餘的SR[j..m]複制到TR
for (l = ; l <= n - j; l++)
{
TR[k + l] = SR[j+l];
}
}
}
}
}
2.非遞歸方式的特點
非遞歸的疊代方法，避免了遞歸時深度為log2(n)的棧空間，空間隻是用到申請歸并臨時用的TR數組，是以空間複雜度為O（n）,并且避免遞歸也在時間性能上有一定的提升，應該說，使用歸并排序時，盡量考慮用非遞歸方式。
若文中有不當或不正确的地方，歡迎指出。虛心求教，謝謝！
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)