归并排序（Merge Sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并操作(Merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。
算法思路：
- 把 n 个记录看成 n 个长度为 l 的有序子表
- 进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表
- 重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。
以数组 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]
function merge(left, right) {
var tmp = [];
while (left.length && right.length) {
if (left[0] < right[0])
tmp.push(left.shift());
else
tmp.push(right.shift());
}
return tmp.concat(left, right);
}
function mergeSort(a) {
if (a.length === 1)
return a;
var mid = ~~(a.length / 2)
, left = a.slice(0, mid)
, right = a.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
