合并排序

合并排序（Merge sort）则是一种被广泛使用的排序方法。

它的基本思想是，将两个已经排序的数组合并，要比从头开始排序所有元素来得快。因此，可以将数组拆开，分成n个只有一个元素的数组，然后不断地两两合并，直到全部排序完成。

以对数组 [3, 2, 4, 5, 1] 进行从小到大排序为例，步骤如下：

• 将数组分成 [3, 2, 4] 和 [5, 1] 两部分。
• 将 [3, 2, 4] 分成 [3, 2] 和 [4] 两部分。
• 将 [3, 2] 分成 [3] 和 [2] 两部分，然后合并成 [2, 3]。
• 将 [2, 3] 和 [4] 合并成 [2, 3, 4]。
• 将 [5, 1] 分成 [5] 和 [1] 两部分，然后合并成 [1, 5]。
• 将 [2, 3, 4] 和 [1, 5] 合并成 [1, 2, 3, 4, 5]。

代码：

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

    while (il < left.length && ir < right.length){
        if (left[il] < right[ir]){
            result.push(left[il++]);
        } else {
            result.push(right[ir++]);
        }
    }
    return result.concat(left.slice(il)).concat(right.slice(ir));
}

function mergeSort(myArray){

    if (myArray.length < 2) {
        return myArray;
    }

    var middle = Math.floor(myArray.length / 2),
        left    = myArray.slice(0, middle),
        right   = myArray.slice(middle),
        params = merge(mergeSort(left), mergeSort(right));
    
    // 在返回的数组头部，添加两个元素，第一个是0，第二个是返回的数组长度
    params.unshift(0, myArray.length);

    // splice用来替换数组元素，它接受多个参数，
    // 第一个是开始替换的位置，第二个是需要替换的个数，后面就是所有新加入的元素。
    // 因为splice不接受数组作为参数，所以采用apply的写法。
    // 这一句的意思就是原来的myArray数组替换成排序后的myArray
    myArray.splice.apply(myArray, params);

    // 返回排序后的数组
    return myArray;
}

原文链接：https://javascript.ruanyifeng.com/library/sorting.html#toc3