合併排序（Merge Sort）

合併排序（merge sort）

進階排序演算法的一種，以「分治法（divide and conquer）」實現，即將大問題拆成多個小問題，一一處理小問題後，就能解決大問題。

圖示

以下可用圖示理解「merge sort」如何以「divide and conquer」方式，將原陣列 [5,4,6,9,8,1,3,2] 由小到大排列。

上半部的「divide」將陣列的長度從 8 縮減為 1，再一一比較每個小陣列中值的大小，並進行排列。

下半部「conquer」排序過程

在陣列長度為 1 時，這八個陣列都已經排序好：

將已經排序好、長度為 1 的陣列兩兩比較，數值較小者先取，組合成已經排序好、長度為 2 的陣列：

排序好長度為 2 的陣列如下：

接著將已經排序好、長度為 2 的陣列兩兩比較，數值小者先取，組合成已經排序好、長度為 4 的陣列：

排序好長度為 4 的陣列如下：

最後將已經排序好、長度為 4 的陣列兩兩比較，數值小者先取，組合成已經排序好、長度為 8 的陣列：

整個陣列最終排序結果如下：

偽代碼&說明

「合併排序」的程式碼分為兩個部分，包含 MERGE() 將兩個已排序的小陣列合併成排序好的大陣列，還有 MERGE-SORT() 實現「分而治之」。

下列偽代碼及程式碼皆以「將陣列由小到大排序」為目標：

第一部分：MERGE()

輸入兩個已經排序好的小陣列「arr1」與「arr2」，透過指標「i」與「j」逐一比較兩陣列中的值，較小者優先放入新建的空陣列「result」。

若其中一陣列全部比較完後，另一陣列仍有未放入「result」的值，因為小陣列的資料都已經排序過，可以直接把小陣列中剩下的值直接搬運到「result」當中。

第二部分：MERGE-SORT()

先取陣列中間值「middle」，接著用「slice()」將陣列分為左右兩邊，直到陣列長度為 1 為止；接著透過遞迴搭配「MERGE()」函數，將小陣列不斷合併、排序，直到輸入的「arr」每筆資料都被排序過為止。

合併排序透過兩個小陣列各自的指標逐一比較、排序，同樣大小的值會按照原順序排在最終結果中，屬於「穩定排序（stable sort）」。

程式碼範例（JavaScript）

//第一部份
function merge(arr1, arr2){
    //製作空陣列result&指標i、j
    let result = [];
    let i = 0;
    let j = 0;

    //將兩陣列合併，並由小到大一一放進result
    while(i < arr1.length && j < arr2.length){
        if(arr1[i] < arr2[j]){
            result.push(arr1[i]);
            i++;
        } else {
            result.push(arr2[j]);
            j++;
        }
    }

    //若arr2比arr1先清空，則將arr1剩下的資料直接搬到result
    while(i < arr1.length){
        result.push(arr1[i]);
        i++;
    }

    //若arr1比arr2先清空，則將arr2剩下的資料直接搬到result
    while(j < arr2.length){
        result.push(arr2[j]);
        j++;
    }

    return result;
}

//第二部分
function mergeSort(arr){
    //遞迴終止條件：arr長度被切為1時
    if(arr.length === 1){
        return arr;
    } else {
        //透過遞迴，先將arr不斷分兩半，再用MERGE()將切小的陣列不斷合併、排序

        //用slice把陣列切兩半，slice括弧內的開始處有包含、結束處不包含
        let middle = Math.floor(arr.length / 2); 
        let left = arr.slice(0, middle); //做一個0到middle-1的小陣列
        let right = arr.slice(middle,arr.length); //做一個middle到arr.length的小陣列

        //用遞迴實現「分而治之」
        return merge(mergeSort(left), mergeSort(right));
        /*
        1. 首先執行括號內的mergeSort：
        左半邊小陣列跟右半邊小陣列都持續對半切，直到所有陣列長度變成1為止，就會到上面的if條件判斷區，回傳arr

        2. mergeSort全部跑完後，接著執行外面的merge：
        將陣列一一用merge比較、合併，持續回傳已經排序好的小陣列，直到整個陣列都被merge為止 
        */
    }
}

時間複雜度

不論最差、最佳或平均情況，皆為 O(n·log n)。

現假設原陣列長度為 n，在逐次分割至長度為 1 的陣列之過程中，每分割一次長度都減半，圖示如下：

由上圖可觀察「分割次數」與「陣列長度」之關係，結果如下表，表中最右方以對數形式呈現的「分割次數」相等於最左方以正整數形式呈現「分割次數」的值：

由右方綠色表格最下方的結論可知：若要將原長度為 n 的陣列切到長度剩下 1，共需要分割 (log₂ n) 次，過程中的每層又有 n 筆資料要處理，因此分割過程的時間複雜度為 O(n·log₂ n)。