内排序7：二路归并排序

归并是指将两个或多个按值有序序列合并成为一个按值有序序列的过程。
二路归并是将两个按值有序序列合并成为一个按值有序序列。
同理，有 三路归并，思路归并等。

归并子算法：
功能是把位置相邻的两个按值有序的序列合并为一个按值有序的序列
具体实现如下：

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++]
    }
}

一趟归并扫描子算法：
功能是将参加排序的序列分成若干长度为t的，且各自按值有序的子序列，然后多次调用归并子算法Merge将所有两两相邻成对的子序列合并成若干个长度为2t的、且各自按值有序的子序列。
具体实现如下：

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]
        }
    }
}

二路归并排序：
就是最初将长度为n的原始序列理解为由n个长度为1的按值有序的子序列组成，并把这些子序列中相邻的子序列两两成对地进行合并，得到[n/2]个长度为2的按值有序子序列（若n为奇数，则还有第[n/2]个子序列，它是原序列中最后那个子序列）；然后将这些子序列又两两成对地进行合并，得到[n/4]个长度为4的按值有序子序列；依次类推，最后只剩一个长度为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))

时间复杂度为O(nlog2n)
空间复杂度为O(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)