/**
 * @description 不修改原数组，返回新数组
 * @param {number[]} left - 需要合并的左数组
 * @param {number[]} right - 需要合并的右数组
 */
export function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr; // 已经有序
  }

  // 分解
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  // 递归地对左右两部分进行归并排序
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);

  // 合并
  return merge(sortedLeft, sortedRight);
}

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  // 比较两个数组的元素，将较小的元素加入结果数组
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // 将剩余的元素加入结果数组
  return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}

export default mergeSort;