排序演算法 | 合併排序

合併排序（英語：Merge sort，或mergesort），是建立在合併操作上的一種有效的排序演算法，效率為O(n log n)（大O符號）。1945年由約翰·馮·紐曼首次提出。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞迴可以同時進行。

使用合併排序為一列數字進行排序的過程：

採用分治法:

分割：遞迴地把目前序列平均分割成兩半。
整合：在保持元素順序的同時將上一步得到的子序列整合到一起（合併）。

合併操作（merge），也叫合併演算法，指的是將兩個已經排序的序列合併成一個序列的操作。合併排序演算法依賴合併操作。

遞迴法（Top-down）
1.申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列
2.設定兩個指標，最初位置分別為兩個已經排序序列的起始位置
3.比較兩個指標所指向的元素，選擇相對小的元素放入到合併空間，並移動指標到下一位置
4.重複步驟3直到某一指標到達序列尾
5.將另一序列剩下的所有元素直接複製到合併序列尾
疊代法（Bottom-up）
原理如下（假設序列共有n個元素）：

1.將序列每相鄰兩個數字進行合併操作，形成ceil(n/2)個序列，排序後每個序列包含兩/一個元素
2.若此時序列數不是1個則將上述序列再次合併，形成ceil(n/4)個序列，每個序列包含四/三個元素
3.重複步驟2，直到所有元素排序完畢，即序列數為1

範例說明

假設現在有一個待排序的序列，[5，2，4，7，1，3，2，2]，那麼我們就需要將該序列進行分治，先將其分成兩份：[5，2， 4，7]和[1，3，2，2]，再將這兩份分別分成兩份：[5，2]和[4，7]；[1，3]和[2，2]，最後將這四部分再次分別分為兩份，最後就將整個序列分為了八份。需要注意的是，在分的過程中，不需要遵循任何規則，關鍵在於合併，合併的過程中便實現了元素的排序。

實作範例(Java)

public static void mergeSort(int[] arr, int left, int right, int[] temp) {
    // 分解
    if (left < right) {
        int mid = (left + right) / 2; // 中間索引
        // 向左遞歸進行分解
        mergeSort(arr, left, mid, temp);
        // 向右遞歸進行分解
        mergeSort(arr, mid + 1, right, temp); // mid + 1，中間位置的後一個位置才是右邊序列的開始位置
        // 每分解一輪便合併一輪
        merge(arr, left, right, mid, temp);
    }
}

/**
 * 合併的方法
 *
 * @param arr 待排序的數組
 * @param left 左邊有序序列的初始索引
 * @param right 中間索引
 * @param mid 右邊有序序列的初始索引
 * @param temp 做中轉的數組
 */
public static void merge(int[] arr, int left, int right, int mid, int[] temp) {
    int i = left; // 初始化i，左邊有序序列的初始索引
    int j = mid + 1; // 初始化j，右邊有序序列的初始索引(右邊有序序列的初始位置即為中間位置的後一個位置)
    int t = 0; // 指向temp數組的當前索引，初始為0
    // 先把左右兩邊的資料(已經有序)按規則填充到temp數組
    // 直到左右兩邊的有序序列，有一邊處理完成為止
    while (i <= mid && j <= right) {
        // 如果左邊有序序列的當前元素小於或等於右邊有序序列的當前元素，就將左邊的元素填充到temp數組中
        if (arr[i] <= arr[j]) {
            temp[t] = arr[i];
            t++; // 索引後移
            i++; // i後移
        } else {
            // 反之，將右邊有序序列的當前元素填充到temp數組中
            temp[t] = arr[j];
            t++; // 索引後移
            j++; // j後移
        }
    }
    // 把有剩餘資料的一邊的元素填充到temp中
    while (i <= mid) {
        // 此時說明左邊序列還有剩餘元素
        // 全部填充到temp數組
        temp[t] = arr[i];
        t++;
        i++;
    }
    while (j <= right) {
        // 此時說明左邊序列還有剩餘元素
        // 全部填充到temp數組
        temp[t] = arr[j];
        t++;
        j++;
    }
    // 將temp數組的元素複製到原數組
    t = 0;
    int tempLeft = left;
    while (tempLeft <= right) {
        arr[tempLeft] = temp[t];
        t++;
        tempLeft++;
    }
}


public static void main(String[] args) {
    int[] arr = {
        3,
        44,
        38,
        5,
        47,
        15,
        36,
        26,
        27,
        2,
        46,
        4,
        19,
        50,
        48
    };
    int[] temp = new int[arr.length];
    mergeSort(arr, 0, arr.length - 1, temp);
    System.out.println(Arrays.toString(arr));
}

結果：

1	[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

對於該排序算法，有兩個部分組成，分解和合併。

首先講分解，在前面也說到了，我們需要將待排序的序列不停地進行分解，通過兩個索引變量控制，一個初始索引，一個結尾索引。只有當兩索引重合才結束分解。此時序列被分解成了十五個小份，這樣分解工作就完成了。

接下來是合併，合併操作也是最麻煩的，也是通過兩個索引變量i，j。開始i在左邊序列的第一個位置，j在右邊序列的第一個位置，然後就是尋找左右兩個序列中的最小值，放到新序列中，這時可能會出現一邊的元素都放置完畢了，而另外一邊還存在元素，此時只需將剩餘的元素按順序放進新序列即可，因為這時左右兩邊的序列已經是有序的了，最後將新序列複製到舊序列。這裡也特別需要注意，因為合併的過程是分步的，而並非一次合併完成，所以數組的索引是在不斷變化的。