介绍

TimSort 是一种混合稳定的排序算法，源自合并排序和插入排序，旨在较好地处理真实世界中各种各样的数据。它的特點是速度快．在最佳狀況只有 O (n)，平均和最糟狀況也有 O (n log (n))。

从 2.3 版本起，TimSort 一直是 Python 的标准排序算法，被 Python 預設的排序函數 sorted () 和 sort () 使用。 它还被 Java SE7, Android platform, GNU Octave, 谷歌浏览器，和 Swift 用于对非原始类型的数组排序。

原理

先把整个资料分成小区块 (称作 Run，一般建议是 32 到 64 个数值，这个数值是 2 的倍数，因为 merge function 对于 2 的倍数的资料数目，处理得比较好。)，分别把小区块的资料以 Insertion Sort 排序，然后再把这些区块以 Merge Sort 的合并阶段作法 (merge function) 来合并起来。

实现

JavaScript

/**
  *  @function Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort,
  *  designed to perform well on many kinds of real-world data.
  *  It was implemented by Tim Peters in 2002 for use in the Python programming language.
  *  It is also used to sort arrays of non-primitive type in Java SE 7,
  *  on the Android platform, in GNU Octave, on V8, Swift and Rust.
  *  1) It sorts small partitions using Insertion Sort.
  *  2) Merges the partition using Merge Sort.
  *  @see [Timsort](https://en.wikipedia.org/wiki/Timsort)
  *  @param {Array} array
  */

const TimSort = (array) => {
  // Default size of a partition
  const RUN = 32
  const n = array.length
  // Sorting the partitions using Insertion Sort
  for (let i = 0; i < n; i += RUN) {
    InsertionSort(array, i, Math.min(i + RUN - 1, n - 1))
  }
  for (let size = RUN; size < n; size *= 2) {
    for (let left = 0; left < n; left += 2 * size) {
      const mid = left + size - 1
      const right = Math.min(left + 2 * size - 1, n - 1)
      Merge(array, left, mid, right)
    }
  }
  return array
}

/**
 * @function performs insertion sort on the partition
 * @param {Array} array array to be sorted
 * @param {Number} left left index of partition
 * @param {Number} right right index of partition
 */

const InsertionSort = (array, left, right) => {
  for (let i = left + 1; i <= right; i++) {
    const key = array[i]
    let j = i - 1
    while (j >= left && array[j] > key) {
      array[j + 1] = array[j]
      j--
    }
    array[j + 1] = key
  }
}

/**
 * @function merges two sorted partitions
 * @param {Array} array array to be sorted
 * @param {Number} left left index of partition
 * @param {Number} mid mid index of partition
 * @param {Number} right right index of partition
 */

const Merge = (array, left, mid, right) => {
  if (mid >= right) return
  const len1 = mid - left + 1
  const len2 = right - mid
  const larr = Array(len1)
  const rarr = Array(len2)
  for (let i = 0; i < len1; i++) {
    larr[i] = array[left + i]
  }
  for (let i = 0; i < len2; i++) {
    rarr[i] = array[mid + 1 + i]
  }
  let i = 0; let j = 0; let k = left
  while (i < larr.length && j < rarr.length) {
    if (larr[i] < rarr[j]) {
      array[k++] = larr[i++]
    } else {
      array[k++] = rarr[j++]
    }
  }
  while (i < larr.length) {
    array[k++] = larr[i++]
  }
  while (j < rarr.length) {
    array[k++] = rarr[j++]
  }
}