带你读《图解算法小抄》十四、排序（8）

// 归并排序基本实现function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}
function merge(left, right) {
  let i = 0;
  let j = 0;
  const merged = [];
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      merged.push(left[i]);
      i++;
    } else {
      merged.push(right[j]);
      j++;
    }
  }
  return merged.concat(left.slice(i)).concat(right.slice(j));
}
// 归并排序优化实现function mergeSortOptimized(arr) {
  if (arr.length <= 16) {
    return insertionSort(arr); // 使用插入排序优化
  }
  const tempArr = new Array(arr.length); // 数组复用，避免重复创建临时数组
  function mergeSortHelper(arr, tempArr, left, right) {
    // 基本实现代码省略
    // 优化合并过程
    if (arr[mid] <= arr[mid + 1]) {
      return; // 已有序，无需合并
    }
    // 基本实现代码省略
  }
  // 基本实现代码省略
  return arr;
}
// 插入排序算法function insertionSort(arr) {
  // 算法实现代码省略}
// 示例用法const array = [5, 3, 8, 4, 2, 1, 6, 7];const sortedArray = mergeSort(array);
console.log(sortedArray); // 输出: [1, 2, 3, 4, 5, 6, 7, 8]