归并排序（MERGE-SORT）基础

定义：归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
实现过程：比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

归并操作

归并排序：其基本思想是分治策略，先进行划分，然后再进行合并。

算法思路

假设要对数组C进行归并排序，步骤是：
let C = [10, 4, 6, 3, 8, 2, 5, 7];
1.先将C划分为两个数组A和B（即把数组C从中间分开 n = Math.floor(C.length/2)）
2.再分别对数组A、B重复步骤1的操作，逐步划分，直到不能再划分为止(每个子数组只剩下一个元素)，这样，划分的过程就结束了。
3.然后从下层往上层不断合并数组，每一层合并相邻的两个子数组，合并的过程是每次从待合并的两个子数组中选取一个最小的元素，然后把这个元素放到合并后的数组中，不断重复直到把两个子数组的元素都放到合并后的数组为止。
4.依次类推，直到合并到最上层结束，这时数据的排序已经完成了。

算法划分和合并过程

先划分： [10, 4, 6, 3, 8, 2, 5, 7]
第一次划分：[10, 4, 6, 3] [8, 2, 5, 7]
第二次划分：[10, 4] [6, 3] [8, 2] [5, 7]
第三次划分：[10] [4] [6] [3] [8] [2] [5] [7]
再合并：
第一次合并：[4, 10] [3, 6] [2, 8] [5, 7]
第二次合并：[3, 4, 6, 10] [2, 5, 7, 8]
第三次合并：[2, 3, 4, 5, 6, 7, 8, 10]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 function　merge(left, right){
	var　result=[];
	while(left.length && right.length){
		if(left[0] < right[0]){
		/*shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。*/
			result.push(left.shift());
		}else{
			result.push(right.shift());
		}
	}
	return　result.concat(left).concat(right);
}
function　mergeSort(items){
	if(items.length === 1){
		return　items;
	}
	let　middle = Math.floor(items.length/2),
		left = items.slice(0, middle), //得到下标从0~index-1的数组
		right = items.slice(middle); //得到下标从index开始到末尾的数组
	return　merge(mergeSort(left), mergeSort(right));
}
let arr = [10, 4, 6, 3, 8, 2, 5, 7];
let demo = mergeSort(arr)
console.log(arr); // [10, 4, 6, 3, 8, 2, 5, 7]
console.log(demo); // [2, 3, 4, 5, 6, 7, 8, 10]

ps：使用递归的代码如下。优点是描述算法过程思路清晰，缺点是使用递归，mergeSort()函数频繁地自我调用。长度为n的数组最终会调用mergeSort()函数 2n-1次，这意味着一个长度超过1500的数组会在Firefox上发生栈溢出错误。可以考虑使用迭代来实现同样的功能。
时间复杂度：O(n log n)
空间复炸都：O（n)
稳定性：稳定
排序方式：外排序