归并排序的基本思想是什么？
归并排序采用分治法（Divide and Conquer），将待排序的数组分成若干个子数组再对子数组进行排序，最后将已排序的子数组合并成一个大的有序数组。
下面是归并排序的基本步骤：
- 分解-Divider：将待排序的数组按照中间位置分成两个子数组，再将每个子数组按照相同的方式分解，直到子数组无法分解为止，即长度为 0 或 1。
- 合并-Conquer：将两个已排序的子数组合并成一个有序的数组，然后将所有的子数组进行合并，直到最后得到完整的有序数组。
归并排序的 JavaScript 实现？
使用自上而下的递归实现：
// 归并函数
function merge(left, right) {
var result = [];
let i = 0,
j = 0,
k = 0;
while (i < left.length && j < right.length) {
// 判断大小
(left[i] <= right[j] && (result[k++] = left[i++]))
||(result[k++]=right[j++]);
}
// 添加剩余元素
while (i < left.length) {
result[k++] = left[i++];
}
// console.log(left, right, result);
while (j < right.length) {
result[k++] = right[j++];
}
return result;
}
// 分解函数
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
// JavaScript 中除法运算会得到小数，因此使用 Math.floor 向下取整
var middle = Math.floor(arr.length / 2);
var left = arr.slice(0, middle);
var right = arr.slice(middle);
// 递归
return merge(mergeSort(left), mergeSort(right));
}
输出：
[ 5 ] [ 4 ] [ 4, 5 ]
[ 2 ] [ 1 ] [ 1, 2 ]
[ 3 ] [ 1, 2 ] [ 1, 2, 3 ]
[ 4, 5 ] [ 1, 2, 3 ] [ 1, 2, 3, 4, 5 ]
[ 1, 2, 3, 4, 5 ]
使用自下而上的迭代实现：
// arr 是原数组，start 为起点，mid 是中间点，end 是终点
function merge(arr, start, mid, end) {
var result = [];
let i = start,
j = mid,
k = 0;
// 开始归并
while (i < mid && j < end) {
(arr[i] <= arr[j] && (result[k++] = arr[i++]))
|| (result[k++] = arr[j++]);
}
// 归并剩余元素
while (i < mid) {
result[k++] = arr[i++];
}
while (j < end) {
result[k++] = arr[j++];
}
//console.log(start, mid, end, result);
// 将结果更新到原数组
for (let i = start; i < end; i++) {
arr[i] = result[i - start];
}
}
function mergeSort(arr) {
// seg为一个分组大小
for (let seg = 1; seg < arr.length; seg *= 2) {
for (let start = 0; start < arr.length; start += seg * 2) {
merge(arr,
start,
Math.min(start + seg, arr.length),
Math.min(start + seg * 2, arr.length));
}
}
}
let arr = [5, 4, 3, 2, 1];
mergeSort(arr);
console.log(arr);
输出：
0 1 2 [ 4, 5 ]
2 3 4 [ 2, 3 ]
4 5 5 [ 1 ]
0 2 4 [ 2, 3, 4, 5 ]
4 5 5 [ 1 ]
0 4 5 [ 1, 2, 3, 4, 5 ]
[ 1, 2, 3, 4, 5 ]
观察到，使用递归和使用迭代实现的归并排序的排序过程是由一定区别的，递归是从两边归并，迭代是从前往后归并。
就记住 mergeSort 函数的作用是 divide，将数组不停从中间分割，然后调用 merge 函数进行 conquer——归并。
归并排序的数组分解需要 O(logn) 次操作，而每一次分解都需要进行 O(n) 时间的合并，所以总的时间复杂度是 O(nlogn)。
归并操作需要 O(n) 的额外空间，如果使用递归的话还有栈空间消耗，为 O(logn)。总的空间复杂度还是 O(n)。
归并排序是否稳定？
稳定的排序指的是原序列中两个相等的元素在排序后先后顺序不变。
稳不稳定看归并排序的归并操作：
while (i < left.length && j < right.length) {
(left[i] <= right[j] && (result[k++] = left[i++]))
||(result[k++]=right[j++]);
}
- left[i] <= right[j]，result[k++] = left[i++]
- left[i] > right[j]，result[k++]=right[j++]
遇到元素相等时，优先处理了左边元素，这保证稳定性。
归并排序的优缺点
归并排序适用于大规模数据的排序，且具有稳定性，但是归并排序需要较大的临时空间来存储排序过程中的数组。
参考资料：
