算法-排序-归并排序

（本文内容来自百度百科）

归并过程

    比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。

归并操作

    归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

    如　设有数列{6，202，100，301，38，8，1}

    初始状态：6,202,100,301,38,8,1

    第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

    第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4； 

    第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

    总的比较次数为：3+4+4=11,逆序数为14。

用途

    速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列.

javaScript

    使用递归的代码如下。优点是描述算法过程思路清晰，缺点是使用递归，mergeSort()函数频繁地自我调用。长度为n的数组最终会调用mergeSort()函数 2n-1次，这意味着一个长度超过1500的数组会在Firefox上发生栈溢出错误。可以考虑使用迭代来实现同样的功能。

function merge(left, right){

    let result = []

    if(!Array.isArray(left) || !Array.isArray(right)){

        return result

    }

    while(left.length>0 && right.length>0){

        if(left[0]>right[0]){

            /*shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。*/

            result.push(left.shift())

        } else {

            result.push(right.shift())

        }

    }

    return result.concat(left).concat(right)

}

function mergeSort(items){

  if(items.length == 1){

    return items

  }

  let middle = Math.floor(items.length/2)

  let left = items.slice(0, middle)

  let right = items.slice(middle)

  return merge(mergeSort(left), mergeSort(right))

}

let arr = [6, 202, 100, 301, 38, 8, 1]

console.log(mergeSort(arr))