归并排序

基本思想：将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

算法过程描述：

将原始数组分割直至只有一个元素的子数组，然后开始归并;
归并过程中完成排序，直至原始数组完全合并并完成排序。

代码实现

JavaScript

const mergeSort = A => {
  // 归--分
  let len = A.length
  if (len < 2) return A
  const mid = len >> 1
  const left = mergeSort(A.slice(0, mid))
  const right = mergeSort(A.slice(mid))
  // 并--治
  const [lenL, lenR, ret] = [left.length, right.length, []]
  let [l, r] = [0, 0] // 定义左右区间指针
  while (--len >= 0) {
    if (l === lenL) {
      ret.push(right[r++])
    } else if (r === lenR) {
      ret.push(left[l++])
    } else if (left[l] > right[r]) {
      ret.push(right[r++])
      // ret.push(left[l++]) // 降序
    } else if (left[l] <= right[r]) {
      ret.push(left[l++])
      // ret.push(right[r++]) // 降序
    }
  }
  return ret
}

稳定性：

若将 第20行 或者 第21行 代码中的>改为>=并且将 第7行 代码中的<=改为<，该算法将不再是稳定排序算法！

算法应用

leetcode

归并排序 ​

代码实现 ​

算法应用 ​

归并排序

代码实现

算法应用