1、歸并排序的基本思想

歸并排序主要是二路歸并排序。二路歸并排序的基本思想，設數(shù)組a中存放了n個數(shù)據(jù)元素，初始時把它們看成是n個長度為1的有序子數(shù)組，然后從第一個有序子數(shù)組開始，把相鄰的有序子數(shù)組兩兩合并，等到n/2個長度為2的新的有序子數(shù)組(當n為奇數(shù)時，最后一個新的有序子數(shù)組的長度為1)。對這些新的有序子數(shù)組再進行兩兩合并。如此重復直到得到一個長度為n的有序數(shù)組為止。
如下如所示是序列{72,73,71,23,94,16,5,68,64}的二路歸并排序過程。

一次二路歸并排序算法的目標是把若干個長度為k的相鄰有序子數(shù)組從前向后進行兩兩歸并，得到個數(shù)減半的長度為2k的相鄰有序子數(shù)組。需要考慮的問題是：若元素個數(shù)是2k的整數(shù)倍，則兩兩歸并正好完成n個數(shù)據(jù)元素的一次二路歸并；若元素個數(shù)不是2k的整數(shù)倍，則當歸并到最后一組時，剩余的元素個數(shù)會不足2k個，這時的處理方法有是:

1. 若剩余的元素個數(shù)大于k而小于2k，則把前k個元素作為一個子數(shù)組，把剩余的元素作為最后一個子數(shù)組。
2. 若剩余的元素個數(shù)小于k時，也就是剩余的元素個數(shù)只夠一組時，則不用再進行兩兩歸并排序。

2、歸并排序的代碼實現(xiàn)

/**
 *
 * @param a 目標序列
 * @param n  目標序列的長度
 * @param swap 一次二路歸并排序后的有序子數(shù)組存于此數(shù)組中
 * @param k 有序子數(shù)組的長度
 */
void Merge(int a[], int n, int swap[], int k) {
    int m = 0, i, j, start2, end1, end2;
    int start1 = 0;//第一個有序子數(shù)組的下界為0
    while (start1 + k <= n - 1) {
        start2 = start1 + k;//計算第二個有序子數(shù)組的下界
        end1 = start2 - 1;//計算第一個有序子數(shù)組的上界
        end2 = (start2 + k - 1 <= n - 1) ? start2 + k - 1 : n - 1;//計算第二個有序子數(shù)組的上界
        //兩個有序子數(shù)組合并
        for (i = start1, j = start2; i < end1 && j < end2; m++) {
            if (a[i] <= a[j]) {
                swap[m] = a[I];
                I++;
            } else {
                swap[m] = a[j];
                j++;
            }
        }
        //子數(shù)組2已經(jīng)歸并完成，將子數(shù)組1中剩余的元素存放到數(shù)組swap中
        while (i <= end1) {
            swap[m] = a[I];
            m++;
            I++;
        }
        //子數(shù)組1已經(jīng)歸并完成，將子數(shù)組2中剩余的元素存放到數(shù)組swap中
        while (j <= end2) {
            swap[m] = a[j];
            m++;
            j++;
        }
        start1 = end2 + 1;
    }
    //將原始數(shù)組中只夠一組的數(shù)據(jù)元素順序存放到數(shù)組swap中
    for (int k = start1; k < n; ++k, m++) {
        swap[m] = a[k];
    }
}

void MergeSort(int a[], int n) {
    int k = 1;
    int *swap;
    swap = (int *) malloc(sizeof(int) * n);//申請動態(tài)數(shù)組空間
    while (k < n) {
        Merge(a, n, swap, k);
        for (int j = 0; j < n; ++j) {
            a[j] = swap[j];//將元素從臨時數(shù)組中放回到數(shù)組a中
        }
        k = 2 * k;//歸并長度加倍
    }
    free(swap);
}

3、歸并排序的效率分析

1. 對n個數(shù)據(jù)元素進行一次二路歸并排序時，歸并的次數(shù)約為，任何一次的二路歸并排序元素的比較次數(shù)都約為n-1，所以二路歸并排序算法的時間復雜度為。
2. 二路歸并排序時使用了n個臨時內(nèi)存單元存放數(shù)據(jù)元素，所以二路歸并排序算法的空間復雜度為。
3. 由于二路歸并排序算法是相鄰子數(shù)組兩兩合并，對于相同的書元素，能夠保證原來在前邊的元素排序后任在前邊，因此二路歸并排序算法是一種穩(wěn)定的排序算法。