归并排序 - javascript

归并排序(mergeSort)，如其名，递归合并；采用分治法；先分，将数组反复二分，直到为一个元素；后治，在分的基础上两两元素对比合并；
归并排序是非常稳定的排序方法，时间复杂幅度最好最坏平均都是NlogN

基本步骤

1. 递归拆分，直到剩下一个元素
2. 两两元素对比合并

如图所示

以上就是基本步骤；
下图是两两数组对比合并的基本步骤：

代码描述

let arr = [5, 4, 3, 6, 9];
function merge(left, right) {
    console.log(left, right);
    // 获得两个数组，排序返回；
    let result = [];
    let i = 0;
    let j = 0;
    // 两个数组进行对比排序，参考上图
    //从第0(用i和j表示)位开始，如果小就push进数组里;
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i++])
        }
        if (left[i] > right[j]) {
            result.push(right[j++])
        }
    }
    if (i < left.length) {
        result.push(...left.slice(i))
    } else {
        result.push(...right.slice(j))
    }
    return result;
}


function mergeSort(arr, type) {
    // debugger
    if (arr.length < 2) {
        return arr
    }
    let catchIndex = Math.floor(arr.length / 2)
    // 循环
    let left = mergeSort(arr.slice(0, catchIndex)); //[5,4]进入循环,再次mergeSort分割left[5],right[4]
    let right = mergeSort(arr.slice(catchIndex)); //[3,6,9]进入循环,再次mergeSort分割left[3],right[6,9]
    // [5, 4, 3, 6, 9];
    // [4,5] [3, 6, 9] 最后执行的left和right；
    //[4] [5] 结束的时候上一个[5,4]会被排序为[4,5]
    //[3] [6,9]
    //[6] [9] 
    //[3] 结束的时候上一个[5,4]会被排序为[3, 6, 9]
    // debugger
    return merge(left, right);
}

合并基本步骤就是

1. 遍历两组数据
2. 进行对比大小
3. 小的那个值取出来放在第一个位置

function merge(left, right) {
    console.log(left, right);
    // 获得两个数组，排序返回；
    let result = [];
    let i = 0;
    let j = 0;
    // 两个数组进行对比排序，参考上图
    //从第0(用i和j表示)位开始，如果小就push进数组里;
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i++])
        }
        if (left[i] > right[j]) {
            result.push(right[j++])
        }
    }
    if (i < left.length) {
        result.push(...left.slice(i))
    } else {
        result.push(...right.slice(j))
    }
    return result;
}