归并排序采纳了分治策略，在对数组进行排序的时候，先将数组宰割成更小的子数组，而后对子数组排序，最初排序后的子数组合并成一个实现的数组，在对子数组排序的时候能够应用雷同的策略持续对子数组进行宰割，直到子数组中只蕴含一个元素。
例如咱们须要数组 [3,2,6,4,8,1,7,5] 排序，首先将数组宰割成只蕴含单个元素的子数组:
[3] [2] [6] [4] [8] [1] [7] [5]将相邻的两个子数组合并，失去蕴含两个元素的已排序子数组：
[2, 3] [4, 6] [1, 8] [5, 7]持续两两合并：
[2, 3, 4, 6] [1, 5, 7, 8]最终就能够失去一个实现的排序好的数组了：
[1, 2, 3, 4, 5, 6, 7, 8]上面看一下怎么用 JS 代码实现一个归并排序。
首先看一下怎么合并两个已排序的子数组，代码如下：
/**
* 辅助办法，合并数组 arr 中的两个已排序的子数组
* 作为例子只思考从小到大排序，其余排序可自定义比拟函数，相似于 Array#sort
* @param {*} arr 数组
* @param {*} start 起始地位
* @param {*} end 完结地位（蕴含在范畴内）* @param {*} mid 两个子数组的宰割地位
*/
function merge(arr, start, end, mid) {
// 须要合并的元素个数
const count = end - start + 1;
// 左侧已排序数组
const left = arr.slice(start, mid + 1);
// 右侧已排序数组
const right = arr.slice(mid + 1, end + 1);
// 退出守卫元素，这样能够不必判断子数组是否为空
left.push(Infinity);
right.push(Infinity);
// 顺次取出两个子数组中的较小的值
let i = 0;
let l = 0;
let r = 0;
while(i < count) {if (left[l] < right[r]) {arr[start + i] = left[l];
l++;
} else {arr[start + i] = right[r];
r++;
}
i++;
}
}
能够把两个已排序的子数组看作是两堆扑克，每次从两队扑克中取出较小的一张牌，直到所有的牌取完，失去的就是一副排好序的扑克。
上面看一下如何应用递归实现归并排序：
首先计算出中心点将数组宰割成两个子数组，对两个子数组别离排序，最初调用 merge 函数将两个已排序的子数组合并失去最终的排序数组。