js算法排序-归并排序

/**
 * 归并排序
 * 采用分治法，
 * 分是将无序列表递归的二分，直到只有一个元素，此时一个元素是有有序的，
 * 治是在每一组都只有一个元素后开始对左右元素比较，处理成小的有序列表，直到所有变为有序
 * @param {*} arr
 */
/**
 * 假设列表为【2,5,4,3】，先分割成只有一个元素的列表[2] [5] [4] [3]
 * 此时left = [2], right =[5]，处理成 [2,5]
 * 此时left = [4], right=[3]， 处理成[3,4]
 * 此时left = [2,5], right = [3,4]， 处理成[2,3,4,5]
 */
function mergeSort(arr) {
    var length = arr.length
    if (length === 1) {
        return arr
    }
    var mid = Math.floor(length / 2)
    var left = arr.slice(0, mid)
    var right = arr.slice(mid)
    return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
    var temp = []
    var i = 0,
        j = 0
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            temp.push(left[i])
            i++
        } else {
            temp.push(right[j])
            j++
        }
    }

    while (i < left.length) {
        temp.push(left[i])
        i++
    }
    while (j < right.length) {
        temp.push(right[j])
        j++
    }
    console.log(temp)
    return temp
}

console.log(mergeSort(arr))