思想
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
image-20200324202429989.png
实现
/**
*
* @param {*} array 排序的原始数组
* @param {*} left 左边有序序列的初始索引
* @param {*} mid 中间索引
* @param {*} right 右边索引
* @param {*} temp 做中转的数组
*/
function merge(array, left, mid, right, temp) {
let i = left //左边有序序列的第一个索引
let j = mid + 1//右边有序序列的第一个索引
let t = 0 //temp的索引
//1. 先把左右两边有序的数据按照规则填充到temp数组
//直到左右两边的有序序列, 有一边处理完为止
while (i <= mid && j <= right) {
if (array[i] <= array[j]) {
temp[t] = array[i]
t++
i++
} else {
temp[t] = array[j]
t++
j++
}
}
//2. 把有剩余的一边的数据依次填充到temp后面
while (i <= mid) {
temp[t] = array[i]
t++
i++
}
while (j <= right) {
temp[t] = array[j]
t++
j++
}
//3. 把temp数组拷贝给array
//注意每次拷贝的长度不一定一样
t = 0
let tempLeft = left
while (tempLeft <= right) {
array[tempLeft] = temp[t]
t++
tempLeft++
}
}
function mergeSort(array, left, right, temp) {//分解
if (left < right) {
let mid = Math.floor((left + right) / 2) //中间索引
mergeSort(array, left, mid, temp)
mergeSort(array, mid + 1, right, temp)
//合并
merge(array, left, mid, right, temp)
}
}
let array = [8, 4, 5, 7, 1, 3, 6, 2]
let temp = new Array(array.length) //需要额外的空间
mergeSort(array, 0, array.length - 1, temp)
console.log(array);
