介绍

归并排序是创建在归并操作上的一种有效的排序算法，效率为 ${\displaystyle O(n\log n)}$。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

原理

采用分治法:

• 分割：递归地把当前序列平均分割成两半。
• 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。

复杂度

• 平均时间复杂度$\Theta (n\log n)$
• 最坏时间复杂度$\Theta (n\log n)$
• 最优时间复杂度$\Theta (n\log n)$
• 空间复杂度$\Theta(n)$

动画

实现

JavaScript

/*
 * MergeSort implementation.
 *
 * Merge Sort is an algorithm where the main list is divided down into two half sized lists, which then have merge sort
 * called on these two smaller lists recursively until there is only a sorted list of one.
 *
 * On the way up the recursive calls, the lists will be merged together inserting
 * the smaller value first, creating a larger sorted list.
 */

/**
 * Sort and merge two given arrays.
 *
 * @param {Array} list1 Sublist to break down.
 * @param {Array} list2 Sublist to break down.
 * @return {Array} The merged list.
 */
function merge (list1, list2) {
  const results = []
  let i = 0
  let j = 0

  while (i < list1.length && j < list2.length) {
    if (list1[i] < list2[j]) {
      results.push(list1[i++])
    } else {
      results.push(list2[j++])
    }
  }

  return results.concat(list1.slice(i), list2.slice(j))
}

/**
 * Break down the lists into smaller pieces to be merged.
 *
 * @param {Array} list List to be sorted.
 * @return {Array} The sorted list.
 */
function mergeSort (list) {
  if (list.length < 2) return list

  const listHalf = Math.floor(list.length / 2)
  const subList1 = list.slice(0, listHalf)
  const subList2 = list.slice(listHalf, list.length)

  return merge(mergeSort(subList1), mergeSort(subList2))
}

参考

• 归并排序 - 维基百科，自由的百科全书 (opens new window)