归并排序（Merge Sort）

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

归并排序（Merge Sort）

例子

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

归并排序步骤模拟图

复杂度

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

参考

维基百科
百度百科

相关阅读

JavaScript的排序算法——冒泡排序
JavaScript的排序算法——选择排序
JavaScript的排序算法——插入排序
JavaScript的排序算法——归并排序
JavaScript的排序算法——快速排序