归并排序

function merge(arr1, arr2) {
  const result = []
  while (arr1.length && arr2.length) {
    if (arr1[0] < arr2[0]) {
      result.push(arr1.shift())
    } else {
      result.push(arr2.shift())
    }
  }
  return result.concat(arr1).concat(arr2)
}

function mergeSort(arr, start, end) {
  if (start >= end) {
    return [arr[start]]
  }
  const mid = Math.floor((start + end) / 2)
  const arr1 = mergeSort(arr, start, mid)
  const arr2 = mergeSort(arr, mid + 1, end)
  return merge(arr1, arr2)
}

function sort(arr) {
  return mergeSort(arr, 0, arr.length - 1)
}

测试代码

console.log(sort([5, 8, 6, 3, 9, 2, 1, 7]))
console.log(sort([3, 4, 2, 1, 5, 6, 7, 8]))
console.log(sort([2, 3, 4, 5, 6, 7, 8, 1]))
console.log(sort([4, 4, 6, 5, 3, 2, 8, 1]))