归并排序

算法模式：二分法

时间复杂度为:O(nlogn)

思路：

1. 二分法递归函数：去中间值下标截取为左右两个数组
2. while 条件判断函数：左右两边进行对比

划分函数 mergeSort

1. 防御性：长度小于 1 直接返回
2. 获取中间值 middle
3. slice 划分 left/right 数组
4. 返回递归数组merge(mergeSort(left), mergeSort(right))

递归数组 merge

4. 声明空数组 result=[]

5. while 条件判断函数

   • 两边都存在 left.length && right.length

     • 左边小于右边：result.push(left.shift())
     • 左边大于右边：result.push(right.shift())

   • 只有左边 left.length

     • 存入 result.push(left.shift())

   • 只有左边 right.length

     • 存入 result.push(left.shift())

const mergeSort = (arr) => {
  if(arr.length <=1) return arr;

  // 二分法
  var middleIndex = Math.floor(arr.length / 2);
  var left = arr.slice(0, middleIndex);
  var right = arr.slice(middleIndex);

  //递归
  return merge(mergeSort(left), mergeSort(right));
}

const merge = (left, right) => {
    const result = [];

     /* while条件判断 */
     // 左右都存在
    while (left.length && right.length) {
        // 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定.
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    // 连接最后一个值：最大值
    // 左边
    while (left.length) result.push(left.shift());
    // 右边
    while (right.length) result.push(right.shift());

    return result;
};

const arr = [5, 4, 3, 2, 1, 6]
console.log(mergeSort(arr))

与快速排序区别：快速排序是对比中间值，归并排序是对比左右

参考文章

• 归并排序算法（JavaScript 实现）