归并排序

归并排序采用分治思想：先把数组拆分成更小的有序数组，再将两个有序数组合并。它的时间复杂度稳定，适合处理大规模数据。

实现

function mergeSort(arr) {
  if (arr.length <= 1) return [...arr]

  const middle = Math.floor(arr.length / 2)
  const left = mergeSort(arr.slice(0, middle))
  const right = mergeSort(arr.slice(middle))
  const result = []
  let i = 0
  let j = 0

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++])
    else result.push(right[j++])
  }

  return result.concat(left.slice(i), right.slice(j))
}

复杂度

• 时间复杂度：O(n log n)
• 空间复杂度：O(n)
• 稳定性：稳定

归并排序适合需要稳定排序的场景，例如按多个字段排序时保留相同元素的原始顺序。