归并排序的基本思想是什么？

采用分治法（Divide and Conquer），递归将待排序的数组平均分成两个子数组，直到子数组长度为 0 或 1，这是 分 Divider。再将排序好的两个子数组合并为一个有序数组，这是 治 Comquer。

---

归并排序的 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++];}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));
}

使用迭代实现

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) {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++]);
}

1. left[i] <= right[j]，result[k++] = left[i++]
2. left[i] > right[j]，result[k++]=right[j++]

遇到元素相等时，优先处理左边元素，这保证稳定性。