一、实现希尔排序
归并排序和快数排序一样采用”分治法“，也就是分而治之；
- 分割：递归地把当前序列平均分割成两半。
- 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。
简单来说就是利用递归每次将数组从中间分成两部分，直到数组的长度小于2后，开始回溯，将分好的两个数组排好序并合成一个新数组，继续回溯直到完成整个算法；
我觉得归并排序的实现没快排难，或者说会快排，写归并就简单很多,这里简单谈一下这两个排序：
- 归并排序的平均时间复杂度为O(nlogn),快排平均时间复杂度也为O(nlogn)；
- 归并排序不是原地排序算法，快速排序是原地算法；
- 快速排序并不稳定，归并排序稳定，也就是快速排序可能会打乱相同元素原本的位置，而归并不会：
二、具体实现
老规矩，先写框架
为什么 let i = gap ? 因为插入排序是从第二个元素开始的，而0+gap = gap 不就是第二个元素的位置吗
为什么 temp < array[index - gap] && index > gap - 1？ 和普通插入排序一样，我们不知道要循环几次，所以用while，比标记元素大则向后移动gap 位，而index>gap -1,是防止index为负数；
function mergeSort(array) {
if (array.length < 2) return array;
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
return result;
}先来实现切割数组的mergeSort函数：
function mergeSort(array) {
// 结束递归条件
if (array.length < 2) return array;
// 拿到中心位置
let center = Math.floor(array.length / 2);
// 分割数组
let left = array.slice(0, center);
let right = array.slice(center);
return merge(mergeSort(left), mergeSort(right));
}，这里要提一下，slice（）方法返回一个新的数组对象，这一对象是一个由?begin?和?end?决定的原数组的浅拷贝（包括?begin，不包括end）。原始数组不会被改变。所以这次拿到中间值是Math.floor(array.length?/?2)，而不是Math.floor(array.length-1?/?2)
接着是用于合并数组的merge函数：
function merge(left, right) {
let result = [];
// 合并的两数组都有值时
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
// 处理一个数组中剩下的值(剩下的可能不只有1个元素)
while (left.length) result.push(left.shift());
while (right.length) result.push(right.shift());
// 返回合并后的数组
return result;
}当需要合并的两个数组都有值时，我们每次比较两个数组的第一个元素，小的放入新数组中，直到其中一个数组没有值；
当需要合并的两个数组中有一个没值时，我们将另一个数组里面的值按顺序放入新数组；
最后返回新数组；
