归并排序

/**
 * @param {number[]} arr 待合并原始数组
 * @param {number} p 左索引，第一个元素的索引
 * @param {number} q 中位索引
 * @param {number} r 右索引，最后一个元素的索引
 *
 * [p, q), [q, r] 均为已排序好的子数组
 *
 * 将 [p,q), [q, r] 合并为一个排序好的数组
 *
 */
const merge = (arr, p, q, r) => {
  // concat 的为哨兵节点
  const arrLeft = arr.slice(p, q + 1).concat(Number.POSITIVE_INFINITY);
  const arrRight = arr.slice(q + 1, r + 1).concat(Number.POSITIVE_INFINITY);

  let indexL = 0;
  let indexR = 0;

  // 注意，遍历从 p 开始，到 r+1
  for (let i = p; i < r + 1; i++) {
    if (arrLeft[indexL] < arrRight[indexR]) {
      arr[i] = arrLeft[indexL];
      indexL++;
    } else {
      arr[i] = arrRight[indexR];
      indexR++;
    }
  }
};

/**
 * 归并排序
 * @param {number[]} arr 待排序数组
 * @param {number} p 左索引 第一个元素的索引
 * @param {number} r 右索引 最后一个元素的索引
 *
 * 思路: 将大数组按中位索引依次拆为更小的两个子数组，将两个子数组排序，然后合并两个排序好的子数组
 *
 * 注意：当拆到最后子数组只有一个元素时，默认为已排序好的，此为递归的终止条件
 */
const mergeSort = (arr, p, r) => {
  if (p < r) {
    let median = Math.floor((p + r) / 2);
    // 排序左数组
    mergeSort(arr, p, median);

    // 排序右数组
    mergeSort(arr, median + 1, r);

    // 合并两个排序好的子数组
    merge(arr, p, median, r);
    // console.log("arr", arr);
  }
  return arr;
};

export { mergeSort };

const arr = [5, 2, 4, 7, 1, 3, 2];
console.log("merge", mergeSort(arr, 0, arr.length - 1));