[TOC]
## 算法原理
> 歸并排序（Merge Sort，臺灣譯作：合并排序）是建立在歸并操作上的一種有效的排序算法。該算法是采用[分治法](http://zh.wikipedia.org/wiki/%E5%88%86%E6%B2%BB%E6%B3%95)（Divide and Conquer）的一個非常典型的應用。
> 歸并操作(Merge)，也叫歸并算法，指的是將兩個已經排序的序列合并成一個序列的操作。歸并排序算法依賴歸并操作。歸并排序有多路歸并排序、兩路歸并排序 , 可用于內排序，也可以用于外排序。這里僅對內排序的兩路歸并方法進行討論。
算法思路：
1. 把 n 個記錄看成 n 個長度為 l 的有序子表
2. 進行兩兩歸并使記錄關鍵字有序，得到 n/2 個長度為 2 的有序子表
3. 重復第 2 步直到所有記錄歸并成一個長度為 n 的有序表為止。
[](https://box.kancloud.cn/2015-07-26_55b4587dc13c6.gif "圖片來自維基百科")圖片來自維基百科
## 實例分析
以數組 array = [6, 5, 3, 1, 8, 7, 2, 4] 為例，首先將數組分為長度為 2 的子數組，并使每個子數組有序：
~~~
[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]
~~~
最后將兩個子數組合并：
~~~
[6, 5, 3, 1, 8, 7, 2, 4]
↓
[1, 2, 3, 4, 5, 6, 7, 8]
~~~
排序過程動畫演示如下：
[](https://box.kancloud.cn/2015-07-26_55b4587e32bc1.gif "圖片來自維基百科")
圖片來自維基百科
再有數組 array = [5, 2, 4, 6, 1, 3, 2, 6]，歸并排序流程也可以如下表示：
[](https://box.kancloud.cn/2015-07-26_55b4587e97149.gif)
## JavaScript 語言實現
屌絲的慣例，上代碼，由于要兩兩歸并的子數組都是有序的數組，同時我們在[希爾排序](http://bubkoo.com/2014/01/15/sort-algorithm/shell-sort/)中提到過“插入排序在對幾乎已經排好序的數據操作時， 效率高， 即可以達到線性排序的效率”，所以我們可以將其中一個子數組中的元素依次插入到另一個數組當中，使其歸并后成為一個有序的數組。代碼如下：
~~~
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](http://en.wikipedia.org/wiki/Merge_sort)
* [維基百科，自由的百科全書](http://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F)
* [Merge Sort](http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/mergeSort.htm)
* [兩路歸并算法](http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.5.1.1.htm)
* [MERGE SORT 動畫演示](http://www.ee.ryerson.ca/~courses/coe428/sorting/mergesort.html)
