1.   mergeSort(arr: number[]) {
  2.       return split(arr, 0, arr.length - 1)
  3.   }
  5.   /**
  6.    * 将数组进行递归分割，直至无法分割后，再进行排序
  7.    * @param arr 
  8.    * @param left 
  9.    * @param right 
  10.    */
  11.     split(arr: number[], left: number, right: number) {
  12.       let mid = Math.floor((left + right) / 2)
  13.       if (left < right) {
  14.           split(arr, left, mid)
  15.           split(arr, mid + 1, right)
  16.           merge(arr, left, mid, right)
  17.       }
  18.         return arr
  19.   }
  21.     /**
  22.    * 将两个分割的排序数组，按从小到大的顺序进行合并
  23.    * @param arr 
  24.    * @param left 
  25.    * @param mid 
  26.    * @param right 
  27.    */
  28.   merge(arr: number[], left: number, mid: number, right: number) {
  29.       const temp: number[] = []
  30.       let i = left
  31.       let j = mid + 1
  33.       // 进行合并排序
  34.       while (i <= mid && j <= right) {
  35.           if (arr[i] > arr[j]) {
  36.               temp.push(arr[i])
  37.               i++
  38.           } else {
  39.               temp.push(arr[j])
  40.               j++
  41.           }
  42.       }
  44.         // 当两个子数组长度不一致时，将剩余部分添加
  45.       while (i <= mid) {
  46.           temp.push(arr[i])
  47.           i++
  48.       }
  50.       while (j <= right) {
  51.           temp.push(arr[j])
  52.           j++
  53.       }
  55.         // Copy 排序后的合并数组到原数组
  56.       for (let m = left; m <= right; m++) {
  57.           arr[m] = temp.shift()!
  58.       }
  59.   }
  61.   swap(arr: number[], i: number, j: number) {
  62.       let temp = arr[i]
  63.       arr[i] = arr[j]
  64.       arr[j] = temp
  65.   }

思路：

使用到了递归，先进行拆解，然后再进行合并。
image.png

递归拆分就不赘述了，合并两个有序数组使用的是双指针法，具体如下图。
image.png
image.png