归并排序（Merge Sort）

在计算机科学里，归并排序（Merge Sort）是一种通用有效的排序算法。通常情况下实现的是稳定的排序队列，这意味着相等元素排序后的顺序与排序前保持一致。归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用，由John von Neumann发明于1945年。

归并排序（Merge Sort）

例子

利用归并排序，对有7个整数值的数组进行排序。以下图示模拟归并排序（自上而下）的步骤。

归并排序步骤模拟图

复杂度

算法	最好情况	平均情况	最坏情况	空间复杂度	稳定性
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定

ES6实现

function MergeSort(array) {
    let len = array.length;
    if (len <= 1) {
      return array;
    }
    let num = Math.floor(len / 2);
    let left = MergeSort(array.slice(0, num));
    let right = MergeSort(array.slice(num, array.length));
    return merge(left, right);
  
    function merge(left, right) {
      let [l, r] = [0, 0];
      let result = [];
      while (l < left.length && r < right.length) {
        if (left[l] < right[r]) {
          result.push(left[l]);
          l++;
        } else {
          result.push(right[r]);
          r++;
        }
      }
      result = result.concat(left.slice(l, left.length));
      result = result.concat(right.slice(r, right.length));
      return result;
    }
  }