归并排序mergeSort

/**
 * @param list 排序列表
 * @param startIndex 开始位置，一般从0开始
 * @param endIndex 结束位置，这里不是结束的索引
 * @returns 排序好的数组
 * @example 
 *  let arr = [5,4,1,3,2]
 *  // 注意endIndex 传的是数组的长度
 *  Mergesort(arr, 0, arr.length);
 *  console.log(arr);
 */
function Mergesort(list: number[], startIndex: number, endIndex: number) {
  let length = Math.floor(endIndex - startIndex);
  if (length <= 1) {
    return;
  } else if (length === 2) {
    let left = list[0];
    let right = list[1];
    if (left > right) {
      list[0] = right;
      list[1] = left;
      return;
    }
  }

  let middleIndex = Math.floor((startIndex + endIndex) / 2);

  Mergesort(list, startIndex, middleIndex);
  Mergesort(list, middleIndex, endIndex);

  const copyList = list.slice(0);

  let leftIndex = startIndex;
  let rightIndex = middleIndex;
  let outputIndex = startIndex;

  while (true) {
    let left = copyList[leftIndex];
    let right = 0;
    if (rightIndex != endIndex) right = copyList[rightIndex];

    let useLeft = left < right;

    if (rightIndex === endIndex) useLeft = true;
    else if (leftIndex === middleIndex) useLeft = false;

    if (useLeft) list[outputIndex++] = copyList[leftIndex++];
    else list[outputIndex++] = copyList[rightIndex++];

    if (leftIndex === middleIndex && rightIndex === endIndex) break;
  }
}

FYI: https://www.youtube.com/watch?v=fEjZrwDKdi8&list=PLW3Zl3wyJwWOpdhYedlD-yCB7WQoHf-My&index=30