归并排序

归并排序又称合并排序

分治算法实现

function mergeSort(arr) {
    //分治算法，将一个数组分成两半，分别排序后合并
    if (arr.length <= 1) {
        return arr; // 如果数组长度小于等于1，直接返回该数组
    }
    const midIndex= Math.floor(arr.length / 2); // 找到中间索引
    const left=mergeSort(arr.slice(0,midIndex)) //分解，递归
    const right=mergeSort(arr.slice(midIndex))
 
    const result=merge(left,right) //合并
  
    return result
}
 
//辅助函数，合并两个切分的数组，变成一个大的有序数组
function merge(left,right){
    let i=0,j=0
    const result=[]
    while(i<left.length&&j<right.length){
        if(left[i]>right[j]){
            result.push(right[j])
            j++;
        }
        else {
            result.push(left[i])
            i++;
        }
    }
    while(i<left.length){
        result.push(left[i])
        i++
    }
    while(j<right.length){
        result.push(right[j])
        j++
    }
    return result
}
 

reference