基本思路

  1. 把数组划分至成多个只有一个元素数组
  2. 将若干个数组两两合并，保证合并后是有序数组
  3. 重复第二步操作直到只剩下一组

时间复杂度 归并排序 - 图1

  1. let mergeSort = (() => {
  2.   return function mergeSort(arr) {
  3.     if (arr.length <= 1) return arr;
  5.     const middleIndex = Math.floor(arr.length / 2);
  6.     const lArr = arr.splice(0, middleIndex);
  7.     const rArr = arr;
  8.     return merge(mergeSort(lArr), mergeSort(rArr));
  9.   };
  11.   function merge(lArr, rArr) {
  12.     const arr = [];
  13.     while (lArr.length && rArr.length) {
  14.       lArr[0] < rArr[0] ? arr.push(lArr.shift()) : arr.push(rArr.shift());
  15.     }
  17.     return arr.concat(lArr, rArr);
  18.   }
  19. })();