归并算法

归并排序是一个可以实际使用的排序算法，复杂度为 $O(n\log n)$。归并排序是一种分而治之算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。

type CompareFunction<T> = (a: T, b: T) => number
 
function merge<T>(left: T[], right: T[], compareFn: CompareFunction<T>) {
  let i = 0
  let j = 0
  const result = []
  while (i < left.length && j < right.length) {
    result.push(compareFn(left[i], right[j]) < 0 ? left[i++] : right[j++])
  }
  return result.concat(i < left.length ? left.slice(i) : right.slice(j))
}
 
function mergeSort<T>(array: T[], compareFn: CompareFunction<T>) {
  const length = array.length
  let tmpArr = array.slice()
 
  if (length > 1) {
    const middle = Math.floor(length / 2)
 
    const left = mergeSort(array.slice(0, middle), compareFn)
    const right = mergeSort(array.slice(middle, length), compareFn)
 
    tmpArr = merge(left, right, compareFn)
  }
 
  return tmpArr
}

时间复杂度 $O(n\log n)$

练习

• LCR 170. 交易逆序对的总数