是什么

归并排序： 分和合的排序算法

怎么用

分

把数组分成2半，在递归分，直到一个单独数字

合

把两个数合并成一个有序数组

function mergeSort(arr) {
  const len = arr.length;
  if (len < 2) return arr;
  let middle = Math.floor(len / 2);
  let left = arr.slice(0, middle);
  let right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
  const result = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }
  return result;
}

const arr = [1, 19, 2, 5, 99, 23];
const res = mergeSort(arr);
console.log(res);

时间复杂度nlogn， 稳定

场景

例如，使用100m内存对900m的数据进行排序，过程如下：

读入100m数据内存，用常规方式排序

将排序后的数据写入磁盘

重复前两个步骤，得到9个100m的临时文件

将100m的内存划分为10份，将9份为输入缓冲区，第10份为输出缓冲区

进行九路归并排序，将结果输出到缓冲区

若输出缓冲区满，将数据写到目标文件，清空缓冲区

若缓冲区空，读入相应文件的下一份数据