前幾天，我發布了一篇快速排序的帖子，今天我們還是圍繞著排序這個話題，繼續講解第二熱度的歸并排序，歸并的遞回版本非常的簡單，非遞回版本的可能稍微要難一點點，但是，不要怕，這都是小問題，我們直接開干！！！

前期文章：

八大排序演算法總結

深入理解快速排序以及優化方式

一、遞回版本

歸并排序的思想：將給定的資料，等分為兩部分，分別遞回呼叫函式，使這兩部分有序，然后再將這左右兩部分的資料進行合并，使其有序，這就是歸并，

如上圖，遞回呼叫綠色部分，使其有序后，再呼叫藍色部分，使其有序后；再將二者進行合并，且還是有序的合并，

所以，在傳入進來的陣列，首先就是進行mid的計算，然后呼叫左部分，再呼叫右部分，最后呼叫merge方法進行合并，

//偽代碼
public void mergeSort(int[] array, int start, int end) {
    int mid = start + (end - start) / 2; //計算中間值
    mergeSort(array, start, mid); //左部分
    mergeSort(array, mid + 1, end); //右部分
    呼叫merge方法進行合并
}

大致框架知道后，現在就是merge方法的實作了，假設我們需要將給定的資料都排升序，則有如下思路：

• 首先開辟一個陣列，大小為end - start + 1，用于臨時存盤已經有序的資料，

• 然后開始拿取左部分和右部分的資料，進行比較，

  • 假設左部分的值小，左部分的值就先放入臨時陣列，然后取出下一個數值
  • 假設右部分的值小，右部分的值就先放入臨時陣列，然后取出下一個數值

• 直到左部分遍歷結束，或者右部分遍歷結束，回圈停止

上面3點過后，回圈停止下來，肯定是因為左部分的資料遍歷完了，或者是右部分的資料遍歷完了，此時肯定有一部分的值還沒有放入臨時陣列，所以還需將沒放入臨時陣列的所有資料，都放入進去，

最后將臨時陣列的所有資料，都放回array原陣列即可，

public void merge(int[] array, int left, int mid, int right) {
    int[] tmp = new int[right - left + 1];
    int p1 = left; //指向左部分陣列的下標
    int p2 = mid + 1; //指向右部分陣列的下標
    int index = 0; //指向臨時陣列的下標
    while (p1 <= mid && p2 <= right) {
        if (array[p1] <= array[p2]) {
           tmp[index] = array[p1]; 
            p1++;
        } else {
            tmp[index] = array[p2];
            p2++;
        }
        index++; //下標后移
    }
    
    while (p1 <= mid) { //左部分的資料還沒遍歷完
        tmp[index] = array[p1];
        index++;
        p1++;
    }
    while (p2 <= right) { //右部分的資料還沒遍歷完
        tmp[index] = array[p2];
        index++;
        p2++;
    }
    
    //將臨時陣列的所有資料，放回array陣列
    for (int i = left; i <= right; i++) {
        array[i] = tmp[i];
    }
}

以上的代碼，就是merge方法，還算是比較簡單的，就是誰的數值更小，誰就先放入臨時陣列即可，

主方法代碼：

public void mergeSort(int[] array, int start, int end) {
    if (start >= end) return;
    
    int mid = start + (end - start) / 2;
    mergeSort(array, start, mid);
    mergeSort(array, mid + 1, end);
    merge(array, start, mid, end);//呼叫合并方法
}

二、非遞回版本

遞回版本的代碼，是從頂至下進行拆分，比如：待排序的陣列的長度是10個，我們可以拆分為5個資料一組，使其有序；而這5個資料，我們還可以拆分為2個資料和3個資料為……，一直往下拆分，

而非遞回版本的代碼，是從底向上，也就是說，第一次，我們拆分為左部分一個資料，右部分一個資料，然后合并；然后再以下一組，左部分一個資料，右部分一個資料，再合并……如下圖：

如上圖，我們先讓每一個小組進行有序后，再呼叫下一趟，使組的資料量擴大一倍即可，

public void mergeSortNoRecur(int[] array) {
    int N = array.length;
    int leftPart = 1; //左部分的元素個數
    while (leftPart < N) {
        int start = 0; //左邊界值
        while (start < N) {
            int mid = start + leftPart - 1; //中間值
            int end = mid + leftPart; //右邊界值
            if (mid > N) break; //中間值，超過陣列長度，直接跳出

            int newEnd = Math.min(end, N); //新右邊界值，與N取最小值，作為這一組的右邊界
            merge(array, start, mid, newEnd); //呼叫merge方法

            start = end + 1; //進入下一組
        }
        leftPart *= 2; //擴大每一個的資料量
    }
}

以上代碼，就是非遞回版本的代碼，最外層的while回圈是躺數，里面的while回圈是用于合并這一趟中各個小組的資料，

歸并的時間復雜度是O(N logN)，空間復雜度是O(N)，

時間復雜度的推導：每次將陣列進行二分，實則拆分下來就是一顆二叉樹，高度就會logN，再對每個節點進行合并，即就是O(N logN)，空間復雜度的推導：每個合并的時候，都會開辟一個陣列，而則這個陣列的長度最大的時候，就是遞回版本代碼中，最后一次的合并操作，也就是第一次拆分為左右部分的時候，即就是O（N），

好啦，本期更新就到此結束啦！我們下期見！！！