歸并排序及其優化

簡單實現

如果有兩個數組已經有序，那么可以把這兩個數組歸并為更大的一個有序數組。歸并排序便是建立在這一基礎上。要將一個數組排序，可以將它劃分為兩個子數組分別排序，然后將結果歸并，使得整體有序。子數組的排序同樣采用這樣的方法排序，這個過程是遞歸的。

下面舉例說明，假如要對數組 a={2,1,3,5,2,3} 進行排序，那么把數組劃分為 {2,1,3} 和 {5,2,3} 兩個子數組，這兩個子數組排序后變為 {1,2,3} 和 {2,3,5} ，然后對這兩個數組進行歸并操作便得到最終的有序數組。代碼實現如下：

void sort(int[] a) {
    int[] aux = new int[a.length];    //輔助數組
    mergeSort(a, 0, a.length - 1, aux);
}

void mergeSort(int[] a, int lo, int hi, int[] aux) {
    if (hi <= lo)
        return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid, aux);
    mergeSort(a, mid + 1, hi, aux);
    merge(a, lo, mid, hi, aux);

}

void merge(int[] a, int lo, int mid, int hi, int[] aux) {
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k];
    }
    for (int k = lo; k <= hi; k++) {
        if (i > mid)
            a[k] = aux[j++];
        else if (j > hi)
            a[k] = aux[i++];
        else if (aux[i] <= aux[j])
            a[k] = aux[i++];
        else
            a[k] = aux[j++];

    }
}

對于歸并排序有幾點說明：

1. 歸并排序的時間復雜度是 O(NLogN) ，空間復雜度是 O(N) 。

2. 輔助數組是一個共用的數組。如果在每個歸并的過程中都申請一個臨時數組會造成比較大的時間開銷。

3. 歸并的過程需要將元素復制到輔助數組，再從輔助數組排序復制回原數組，會拖慢排序速度。

優化

歸并排序有以下幾點優化方法：

1. 和快速排序一樣，對于小數組可以使用插入排序或者選擇排序，避免遞歸調用。

2. 在 merge() 調用之前，可以判斷一下 a[mid] 是否小于等于 a[mid+1] 。如果是的話那么就不用歸并了，數組已經是有序的。原因很簡單，既然兩個子數組已經有序了，那么 a[mid] 是第一個子數組的最大值， a[mid+1] 是第二個子數組的最小值。當 a[mid]<=a[mid+1] 時，數組整體有序。

3. 為了節省將元素復制到輔助數組作用的時間，可以在遞歸調用的每個層次交換原始數組與輔助數組的角色。

4. 在 merge() 方法中的歸并過程需要判斷 i 和 j 是否已經越界，即某半邊已經用盡。可以用另一種方式，去掉檢測是否某半邊已經用盡的代碼。具體步驟是將數組 a[] 的后半部分以降序的方式復制到 aux[] ，然后從兩端歸并。對于數組 {1,2,3} 和 {2,3,5} ,第一個子數組照常復制，第二個則從后往前復制，最終 aux[] 中的元素為 {1,2,3,5,3,2} 。這種方法的缺點是使得歸并排序變為 不穩定 排序。代碼實現如下：

   void merge(int[] a, int lo, int mid, int hi, int[] aux) {
   for (int k = lo; k <= mid; k++) {
       aux[k] = a[k];
   }
   for (int k = mid + 1;k <= hi; k++) {
       aux[k] = a[hi - k + mid + 1];
   }
   int i = lo, j = hi;      //從兩端往中間
   for (int k = lo; k <= hi; k++)
       if (aux[i] <= aux[j]) a[k] = aux[i++];
       else a[k] = aux[j--];
   }

另一種實現：自底向上的歸并排序

在上面的實現中，相當于將一個大問題分割成小問題分別解決，然后用所有小問題的答案來解決整個大問題。將一個大的數組的排序劃分為小數組的排序是自頂向下的排序。還有一種實現是自底向上的排序，即先兩兩歸并，然后四四歸并......代碼實現如下：

void sort(int[] a) {
    int N = a.length;
    int[] aux = new int[N];
    for (int sz = 1; sz < N; sz += sz) {
        for (int lo = 0; lo < N - sz; lo += sz + sz) {
            //在每輪歸并中，最后一次歸并的第二個子數組可能比第一個子數組要小
            merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1), aux);
        }
    }
}