（7）歸并排序 (Merge Sort)

算法原理

歸并排序（Merge Sort，臺灣譯作：合并排序）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。

歸并操作(Merge)，也叫歸并算法，指的是將兩個已經(jīng)排序的序列合并成一個序列的操作。歸并排序算法依賴歸并操作。歸并排序有多路歸并排序、兩路歸并排序 , 可用于內(nèi)排序，也可以用于外排序。這里僅對內(nèi)排序的兩路歸并方法進行討論。

算法思路：

1. 把 n 個記錄看成 n 個長度為 l 的有序子表
2. 進行兩兩歸并使記錄關(guān)鍵字有序，得到 n/2 個長度為 2 的有序子表
3. 重復(fù)第 2 步直到所有記錄歸并成一個長度為 n 的有序表為止。

圖片來自維基百科

實例分析

以數(shù)組 array = [6, 5, 3, 1, 8, 7, 2, 4] 為例，首先將數(shù)組分為長度為 2 的子數(shù)組，并使每個子數(shù)組有序：

[6, 5]  [3, 1]  [8, 7]  [2, 4]
   ↓       ↓       ↓       ↓
[5, 6]  [1, 3]  [7, 8]  [2, 4]

然后再兩兩合并：

[6, 5, 3, 1]  [8, 7, 2, 4]
      ↓             ↓
[1, 3, 5, 6]  [2, 4, 7, 8]

最后將兩個子數(shù)組合并：

[6, 5, 3, 1, 8, 7, 2, 4]
            ↓
[1, 2, 3, 4, 5, 6, 7, 8]

排序過程動畫演示如下：

圖片來自維基百科

再有數(shù)組 array = [5, 2, 4, 6, 1, 3, 2, 6]，歸并排序流程也可以如下表示：

JavaScript 語言實現(xiàn)

屌絲的慣例，上代碼，由于要兩兩歸并的子數(shù)組都是有序的數(shù)組，同時我們在希爾排序中提到過“插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時， 效率高， 即可以達(dá)到線性排序的效率”，所以我們可以將其中一個子數(shù)組中的元素依次插入到另一個數(shù)組當(dāng)中，使其歸并后成為一個有序的數(shù)組。代碼如下：

function mergeSort(array) {

    function sort(array, first, last) {
        first = (first === undefined) ? 0 : first
        last = (last === undefined) ? array.length - 1 : last
        if (last - first < 1) {
            return;
        }
        var middle = Math.floor((first + last) / 2);
        sort(array, first, middle);
        sort(array, middle + 1, last);

        var f = first,
            m = middle,
            i,
            temp;

        while (f <= m && m + 1 <= last) {
            if (array[f] >= array[m + 1]) { // 這里使用了插入排序的思想
                temp = array[m + 1];
                for (i = m; i >= f; i--) {
                    array[i + 1] = array[i];
                }
                array[f] = temp;
                m++
            } else {
                f++
            }
        }

        return array;
    }

    return sort(array);
}

參考文章

• Wikipedia
• 維基百科，自由的百科全書
• Merge Sort
• 兩路歸并算法
• MERGE SORT 動畫演示