算法-合并排序

合并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略

• 其基本模式如下：
  分解：把一个问题分解成与原问题相似的子问题
  解决：递归的解各个子问题
  合并：合并子问题的结果得到了原问题的解。

动态效果示意图：

分阶段：递归拆分子序列的过程。
治阶段：将两个已经有序的子序列合并成一个有序序列

/**
 * 合并排序算法
 * @param {Arry[number]} arr 待排序数组
 */
function mergeSort(arr) {
    // 采用自上而下的递归方法
    var len = arr.length;
    if (len < 2) {//只有1个数就返回
        return arr;
    }
    var middle = Math.floor(len / 2),//中间值
        left = arr.slice(0, middle),//左边数组
        right = arr.slice(middle);//右边数组
    return merge(mergeSort(left), mergeSort(right));
}

/**
 * 把两个数组合并排序
 * @param {Arry[number]}} left 待合并数组
 * @param {Arry[number]} right 待合并数组
 */
function merge(left, right) {
  var result = [];

  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;
}

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序。每次合并操作的平均时间复杂度为O(n)，总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。