归并排序

• 时间复杂度（平均）：O(n * long2(n))
• 时间复杂度（最坏）：O(n * long2(n))
• 时间复杂度（最好）：O(n * long2(n))
• 空间复杂度：O(n)
• 稳定

算法

归并算法是采用分治法的典型应用

函数mergeSort将arr分成长度为1的子数组，然后重复调用merge函数，将这些长度为1的子数组按递增的顺序合并成长度为2的子数组，然后合并成长度为4的子数组。。。

function mergeSort(arr) {
	if (arr.length < 2) {
		return arr;
	}
	const middle = Math.floor(arr.length / 2);
	const left = arr.slice(0, middle);
	const right = arr.slice(middle);
	return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
	const res = [];
	while (left.length && right.length) {
		if (left[0] <= right[0]) {
			res.push(left.shift());
		} else {
			res.push(right.shift());
		}
	}
	while (left.length) {
		res.push(left.shift());
	}
	while (right.length) {
		res.push(right.shift());
	}
	return res;
}