编辑代码

var array = [1, 9, 2, 1, 5, 2, 3, 7, 7]

console.log('== 归并排序 ==\n')

console.log(`归并排序是第一个可以被实际使用的排序算法。你在本书中学到的前三个排序算法（冒泡、选择、插入）性能不
好，但归并排序性能不错，其复杂度为O(nlogn)。\n`)

console.log(`归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一
个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。\n`)

function createRandomArray(size) {
    var arr = []
    for (let i = 0; i < size; i++) {
        arr.push(Math.round(Math.random() * size))
    }
    array = arr
    return arr
}

function mergeSort() {

}
/**
 * 规定排序--分而治之
 * 先排序两个单数据数组，再排序两个已排序数组
 * 比较两个数组首位数，小的先放进result,
 * 
 *  i【2，4】-- j【3，5】 两个已排序数组排序
 *  i=0,j=0,result=[]
 *  2<3 --> result=[2] i++ i=1
 *  4>3 --> result=[2,3] j++ j=1
 *  4<5 --> result=[2,3,4] i++ i=2 终止首个while
 * 
 *  i<2 否 终止left while
 *  j<2 是 j++ j=2 终止right while
 *  循环结束，得到排序数组result=[2,3,4，5]
 */

/**
 * 对两个数组进行排序，合并成一个数组
 * 左右数组特点是已排序数组，因此比较时只用拿数组首位比较
 */


function merge1(left, right) {
    // [3] [2]
    var result = []

    // console.log('\n比较数据', left, right)

    var shiftL = left.shift()
    var shiftR = right.shift()

    // 自己琢磨的排序写法
    while (shiftL != undefined || shiftR != undefined) {
        if (shiftL !== undefined && shiftR !== undefined) {

            if (shiftL >= shiftR) {
                result.push(shiftR)
                shiftR = right.shift()
            } else {
                result.push(shiftL)
                shiftL = left.shift()
            }
        }

        if (shiftL != undefined && shiftR == undefined) {
            result.push(shiftL)
            shiftL = left.shift()
        }

        if (shiftR != undefined && shiftL == undefined) {
            result.push(shiftR)
            shiftR = right.shift()
        }

    }


    return result

}


function merge(left, right) {
    // [3] [2]
    var result = [],
        il = 0,
        ir = 0

    // 官方给的排序写法
    while (il < left.length && ir < right.length) {
        if (left[il] < right[ir]) {
            result.push(left[il++])
        } else {
            // 3>2  ->[2]
            result.push(right[ir++])
        }
    }

    while (il < left.length) {
        // 3>2->[2].push(3)
        result.push(left[il++])
    }

    while (ir < left.length) {
        result.push(right[ir++])
    }
    // 可以看到，算法首先将原始数组分割直至只有一个元素的子数组，然后开始归并。归并过程
    // 也会完成排序，直至原始数组完全合并并完成排序。
    // [2,3]
    return result

}

// 辅助函数
function mergeSortRec(array, num) {
    var len = array.length
    if (len == 1) {
        return array
    }

    var mid = Math.floor(len / 2),
        left = array.slice(0, mid),
        right = array.slice(mid, len)
    if (num) {
        return merge1(mergeSortRec(left), mergeSortRec(right))
    } else {
        return merge(mergeSortRec(left), mergeSortRec(right))
    }

}
// 排序流程
// [3,2,1,6,4]
// [3,2] [1,6,4]
// [3][2] [1][6,4]
// [2,3] [1][6][4]
// [2,3] [1][4,6]
// [2,3] [1,4,6]
// [1,2,3,4,6]


createRandomArray(9)
array = [1, 3, 7, 6, 7, 8, 9, 2, 3]
console.log('排序前：', array)
console.time('耗时')
array = mergeSortRec(array)
console.timeEnd('耗时')
console.log('排序后数组：', array)

console.log('\n')

createRandomArray(9)
array = [1, 3, 7, 6, 7, 8, 9, 2, 3]
console.log('排序前：', array)
console.time('耗时1')
array = mergeSortRec(array, 1)
console.timeEnd('耗时1')

console.log('排序后数组：', array)