这系列文章是慕课网《算法与数据结构》实战课程老师的讲授内容笔记整理，其中有很多动图都是我参考老师的动画演示自己制作的，并提供 JS(es6) 版的代码示例。代码仓库：📦 https://github.com/Mitscherlich/Play-with-Algorithms-JS

 比  快多少？

归并排序

1. 将一个数组一分为二，分别对两个子数组进行排序；

2. 对子数组排序时，继续将子数组分为两部分，直到每部分只有不多于 1 个元素 (并不一定，接下来会有说明)；

3. 逐级向上归并，得到排序后的数组。

归并过程

1. 比较 i 与 j 索引位置元素的大小，将较小(或大)的元素放置到原数组索引 k 的位置上；

2. 重复此步骤，直到 i 或者 j 超出子数组索引范围；

3. 若子数组仍有剩余元素，则依次放置到原数组末尾，直到子数组均遍历完成。

// 将 arr[l...mid] 和 arr[mid+1...r] 两部分进行归并
function merge (array, l, mid, r, cb) {
  const aux = new Array(r - l + 1)
  for (let i = l; i <= r; i++) {
    aux[i - l] = array[i]
  }
  // 初始化，i 指向左半部分的起始索引位置 l；j 指向右半部分起始索引位置 mid+1
  let i = l
  let j = mid + 1
  for (let k = l; k <= r; k++) {
    if (i > mid) { // 如果左半部分元素已经全部处理完毕
      array[k] = aux[j++ - l]
    } else if (j > r) { // 如果右半部分元素已经全部处理完毕
      array[k] = aux[i++ - l]
    } else if (cb(aux[i - l], aux[j - l])) { // 左半部分所指元素 < 右半部分所指元素
      array[k] = aux[i++ - l]
    } else { // 左半部分所指元素 >= 右半部分所指元素
      array[k] = aux[j++ - l]
    }
  }
}

// 递归使用归并排序, 对 arr[l...r] 的范围进行排序
function mergeSort (array, l, r, cb) {
  if (l >= r) {
    return
  }
  const mid = Math.floor((l + r) / 2)
  mergeSort(array, l, mid, cb)
  mergeSort(array, mid + 1, r, cb)
  merge(array, l, mid, r, cb)
}

Array.prototype.mergeSort = function (cb) {
  const array = this.slice()
  const n = array.length
  mergeSort(array, 0, n - 1, cb)
  return array
}

function insertSortPartial (array, l, cb) {
  for (let i = l + 1; i <= r; i++) {
    let e = array[i]
    let j
    for (j = i; j > l && !cb(array[j - 1], e); j--) {
      array[j] = array[j - 1]
    }
    array[j] = e
  }
  return array
}

// 递归使用归并排序, 对 arr[l...r] 的范围进行排序
function mergeSortEnhance (array, l, r, cb) {
  // 优化 1: 对于小规模数组, 使用插入排序
  if (r - l <= 15) {
    array = insertSortPartial(array, l, r, cb)
    return
  }
  const mid = Math.floor((l + r) / 2)
  mergeSortEnhance(array, l, mid, cb)
  mergeSortEnhance(array, mid + 1, r, cb)
  // 优化 2: 对于 arr[mid] <= arr[mid+1] 的情况, 不进行 merge
  // 对于近乎有序的数组非常有效, 但是对于一般情况, 有一定的性能损失
  if (!cb(array[mid], array[mid + 1])) {
    merge(array, l, mid, r, cb)
  }
}

Array.prototype.mergeSortEnhance = function (cb) {
  const array = this.slice()
  const n = array.length
  mergeSortEnhance(array, 0, n - 1, cb)
  return array
}

自顶向下的归并排序

Array.prototype.mergeSortReverse = function (cb) {
  const array = this.slice()
  const n = array.length
  for (let sz = 1; sz <= n; sz += sz) {
    for (let i = 0; i + sz < n; i += sz + sz) {
      // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
      merge(array, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1), cb)
    }
  }
  return array
}

// Merge Sort Bottom Up 优化
Array.prototype.mergeSortReverseEnhance = function (cb) {
  const array = this.slice()
  const n = array.length
  // 对于小数组, 使用插入排序优化
  for (let i = 0; i < n; i += 16) {
    insertSortPartial(array, i, Math.min(i + 15, n - 1), cb)
  }

  for (let sz = 16; sz < n; sz += sz) {
    for (let i = 0; i + sz < n; i += sz + sz) {
      // 对于 arr[mid] <= arr[mid+1] 的情况, 不进行 merge
      if (!cb(array[i + sz - 1], array[i + sz])) {
        merge(array, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1), cb)
      }
    }
  }
  return array
}

小结