算法步骤

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4. 重复步骤 3 直到某一指针达到序列尾；
5. 将另一序列剩下的所有元素直接复制到合并序列尾。

Code:

/**
 @Project :算法
 @File : index1
 @IDE : WebStorm
 @Author : xinyu
 @Date :2022/3/2 下午6:10
 @Description :归并排序性能较好
 **/
import baseFunction = require("../utils/baseUtils");
let baseFunctions = new baseFunction()

let mergaSort = (array,compareFn=baseFunctions.defaultCompare)=>{
    if (array.length>1){
        const {length} = array
        const middle = Math.floor(length/2)
        const left = mergaSort(array.slice(0,middle),compareFn)
        const right = mergaSort(array.slice(middle,length),compareFn)
        array =baseFunctions.merge(left,right,compareFn)
    }
    return array
}
console.log(baseFunctions.testArray);
console.log(mergaSort(baseFunctions.testArray));