歸并是指將兩個(gè)或多個(gè)按值有序序列合并成為一個(gè)按值有序序列的過程蜂科。
二路歸并是將兩個(gè)按值有序序列合并成為一個(gè)按值有序序列顽决。
同理，有 三路歸并导匣，思路歸并等才菠。

歸并子算法：
功能是把位置相鄰的兩個(gè)按值有序的序列合并為一個(gè)按值有序的序列
具體實(shí)現(xiàn)如下：

var merge = function(X, Z, s, u, v) {
    //將有序的x[s..u]和x[u+1..v]歸并為有序的x[s..v]
    let i, j, q
    i = s
    j = u + 1
    q = s

    while (i <= u && j <= v) {
        if (X[i] < X[j]) {
            Z[q++] = X[i++]
        } else {
            Z[q++] = X[j++]
        }
    }

    while (i <= u) {
        Z[q++] = X[i++]
    }
    while (j <= v) {
        Z[q++] = X[j++]
    }
}

一趟歸并掃描子算法：
功能是將參加排序的序列分成若干長(zhǎng)度為t的，且各自按值有序的子序列贡定，然后多次調(diào)用歸并子算法Merge將所有兩兩相鄰成對(duì)的子序列合并成若干個(gè)長(zhǎng)度為2t的赋访、且各自按值有序的子序列。
具體實(shí)現(xiàn)如下：

var mpass = function(X, Y, n, t) {
    let i = 0;
    while (n - i + 1 > 2 * t) {
        merge(X, Y, i, i + t - 1, i + 2 * t - 1)
        i = i + 2 * t
    }
    if (n - i + 1 > t) {
        merge(X, Y, i, i + t - 1, n - 1)
    } else {
        for (let j = i; j < n; j++) {
            Y[j] = X[j]
        }
    }
}

二路歸并排序：
就是最初將長(zhǎng)度為n的原始序列理解為由n個(gè)長(zhǎng)度為1的按值有序的子序列組成缓待，并把這些子序列中相鄰的子序列兩兩成對(duì)地進(jìn)行合并蚓耽，得到[n/2]個(gè)長(zhǎng)度為2的按值有序子序列（若n為奇數(shù)，則還有第[n/2]個(gè)子序列旋炒，它是原序列中最后那個(gè)子序列）步悠；然后將這些子序列又兩兩成對(duì)地進(jìn)行合并，得到[n/4]個(gè)長(zhǎng)度為4的按值有序子序列瘫镇；依次類推鼎兽，最后只剩一個(gè)長(zhǎng)度為n的子序列，這個(gè)子序列就是原始序列經(jīng)過二路歸并排序后的結(jié)果铣除。
具體實(shí)現(xiàn)如下：

var mergeSort = function(X) {
    let t = 1
    let n = X.length
    let Y = []
    let isx = false
    while (t < n) {
        mpass(X, Y, n, t)
        isx = false
        t *= 2
        if (t <= n) {
            mpass(Y, X, n, t)
            isx = true
        }
        t *= 2
    }
    return isx? X:Y
}
var arr = [5, 3, 8, 1, 9, 2, 7, 4, 6, 10]
console.log(mergeSort(arr))

時(shí)間復(fù)雜度為O(nlog2n)
空間復(fù)雜度為O(n)
是穩(wěn)定排序

第二種方法：

function mergeSort(arr) {  // 采用自上而下的遞歸方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}
var arr = [5,3,8,1,9,2,7,4,6,10]
mergeSort(arr)