归并排序

选择排序的复杂度是O(nlogn)级别，归并排序利用的递归。

// 归并排序
function mergeSort(arr) {
  // 处理从第0个位置开始，到数组的最后一个位置
  __mergeSort(arr, 0, arr.length - 1);
  return arr;
}
// 对[l, r]区间的元素进行排序
function __mergeSort(arr, l, r) {
  // 递归到底的情况
  if (l >= r) {
    return;
  }
  // 在需要排序的元素数量较少时，可以转为使用插入排序，因为元素数量较少时，插入排序会更快
  // if (r - l <= 15) {
  //   insertSortRange(arr, l, r)
  //   return
  // }
  // 计算区间的中点位置
  let mid = Math.floor((l + r) / 2);
  // 对[l, mid]区间的元素进行排序
  __mergeSort(arr, l, mid);
  // 对[mid + 1, r]区间的元素进行排序
  __mergeSort(arr, mid + 1, r);
  // 只有当mid位置元素大于mid + 1位置元素时才需要排序
  if (arr[mid] > arr[mid + 1]) {
    // 对[l, mid]和[mid + 1, r]两个部分进行归并
    __merge(arr, l, mid, r);
  }
}
function __merge(arr, l, mid, r) {
  // 创建一个新数组，方便赋值
  let space = [];
  // 将[l, r]的元素都存储到新数组中
  for (let i = l; i <= r; i++) {
    space[i - l] = arr[i];
  }
  // i表示左半部分正在对比的元素，j表示右半部分正在对比的元素
  let i = l,
    j = mid + 1;
  // 判断[l, r]的所有元素
  for (let k = l; k <= r; k++) {
    // 左半部分已经归并完成，没有元素时
    if (i > mid) {
      arr[k] = space[j - l];
      j++;
    } else if (j > r) {
      // 右半部分已经归并完成，没有元素时
      arr[k] = space[i - l];
      i++;
    } else if (space[i - l] < space[j - l]) {
      // 左半部分元素小于右半部分元素
      arr[k] = space[i - l];
      i++;
    } else {
      // 右半部分元素小于左半部分元素
      arr[k] = space[j - l];
      j++;
    }
  }
}
// 自底向上归并
function mergeSortBtoU(arr) {
  // 从底部开始归并，第一次归并2个元素，第二次归并4个元素，第三次归并8个元素，以此类推
  for (let size = 1; size <= arr.length; size += size) {
    // i + size可能超过arr.length的大小，所以循环结束条件为i + size小于arr.length
    for (let i = 0; i + size < arr.length; i += size + size) {
      // i + size + size - 1可能超过arr.length的大小，所以要取两者的较小一方
      __merge(arr, i, i + size - 1, Math.min(i + size + size - 1, arr.length - 1));
    }
  }
  return arr;
}