基本思想：把一個長度為n 的無序序列看成是 n 個長度為 1 的有序子序列 悦穿，首先做兩兩歸并羹膳，得到 [n / 2] 個長度為 2 的有序子序列 ；再做兩兩歸并肠套，…舰涌，如此重復(fù)，直到最后得到一個長度為 n 的有序序列你稚。

實(shí)現(xiàn)代碼：

一次二路歸并算法：

static void Merge(int[] a, int[] swap, int k, int n)
{//swap用于存放一次歸并后的數(shù)組瓷耙，k為有序子數(shù)組長度，n為數(shù)組大小

    int i, j, low1, up1, low2, up2, m;
    low1 = 0; //第一個子數(shù)組下界為0
    m = 0;  //swap數(shù)組下標(biāo)
    while (low1 + k <= n - 1)
    {
        low2 = low1 + k;//第二個子數(shù)組下界
        up1 = low2 - 1; //第一個子數(shù)組上界
        //第二個子數(shù)組上界需要考慮是否超出數(shù)組范圍入宦，超出則直接等于最后下標(biāo)
        up2 = (low2 + k - 1 <= n - 1) ? low2 + k - 1 : n - 1;
        //同時遍歷兩個子數(shù)組，直到任意一個遍歷完
        for (i = low1, j = low2; i <= up1 && j <= up2; m++)
        {//從小到大依次存到swap數(shù)組中
            if (a[i] <= a[j])
            {
                swap[m] = a[i];
                i++;
            }
            else
            {
                swap[m] = a[j];
                j++;
            }
        }
        //將未遍歷完的子數(shù)組剩下的元素存放到swap中
        while (i <= up1)
        {
            swap[m] = a[i];
            m++;
            i++;
        }
        while (j <= up2)
        {
            swap[m] = a[j];
            m++;
            j++;
        }

        low1 = up2 + 1;//跳到下兩個子數(shù)組室琢，循環(huán)繼續(xù)
    }
    //把剩下只夠一組的數(shù)據(jù)依次放到swap的最后面
    for (i = low1; i < n; i++, m++)
    {
        swap[m] = a[i];
    }
}

二路歸并算法：

static void MergeSoprt(int[] a, int n)
{
    int i, k = 1;
    int[] swap = new int[n];
    while (k < n)
    {
        Console.WriteLine("有序子數(shù)組長度 = " + k);
        Merge(a, swap, k, n);
        for (i = 0; i < n; i++)
        {
            a[i] = swap[i];
            Console.Write(a[i] + " ");
        }
        Console.WriteLine();
        k *= 2;
    }
}

測試代碼：

static void Main(string[] args)
{
    int[] nums = { 21, 25, 49, 25, 93, 62, 72, 8, 37, 16, 54 };
    MergeSoprt(nums, nums.Length);

    Console.ReadKey();
}

總結(jié)：
1乾闰、合并就是兩個數(shù)組里的元素相互比較，從小到大存到一個新數(shù)組中盈滴；
2涯肩、時間效率： O(nlog2n)
3轿钠、穩(wěn)定性：穩(wěn)定

最后總結(jié)：

思考：
1、若初始記錄基本有序病苗，則選用哪些排序方法比較適合疗垛？
答：可選用直接插入、簡單選擇硫朦、堆排序贷腕、冒泡排序、歸并排序咬展、(希爾排序)等方法泽裳，其中最快的是
插入排序和冒泡排序，因?yàn)橹挥斜容^動作破婆，無需移動元素涮总。此時平均時間復(fù)雜度為O(n)。
2祷舀、若初始記錄基本無序瀑梗，最好選用哪些排序方法？
答：最好選用快速裳扯、希爾抛丽、歸并、堆排序等嚎朽，這些算法的共同特點(diǎn)是铺纽，通過“振蕩”讓數(shù)值相差不大但位置差異很大的元素盡快到位。