合并排序（MERGE-SORT）是一种基于合并操作的有效排序算法，是分治法（DivideandConquer）非常典型的应用。将有序的子序列组合起来，得到一个完全有序的序列；即先把每个子序列排好序，再把子序列段排好序。将两个排序列表合并为一个排序列表称为双向合并。归并排序归并排序是一种非常稳定的排序方法，其时间复杂度平均、最好、最差为NlogN。归并排序的两步是先分裂，直到只分裂出一个数，然后开始递归合并分裂过程。从上图可以看出，归并排序会将一个数组成对拆分，一直拆分，只有一个数时停止拆分。那么拆分的代码就很简单了，就是得到一个指向中间的指针q，将数组拆分为(start,p)和(p,end)两部分。p表示数组的起始下标r表示数组的结束下标functiondivide(p,r){returnMath.floor((p+r)/2);}合并过程合并的过程如上图遍历两组数据进行比较，取出较小的值放在第一个位置。例如：假设数组A的数据是[2,5,1,3]，经过我们的拆分后就是(0,2),(2,4)；我们通过A.slice(0,2)和A.slice(2,4)得到两个数组A1[2,5]和A2[1,3]=>然后我们将数组[2,5,1,3]到遍历，第一次取两边较小的数1，第二次2，第三次3，第四次5functionmerge(A,p,q,r){constA1=A.slice(p,q);constA2=A.slice(q,r);//Sentry，比如给A1和A2压一个最大值，防止A1里面的数比较小，导致第一次遍历一个数组三次没有值A1.push(Number.MAX_SAFE_INTEGER);A2.push(Number.MAX_SAFE_INTEGER);//循环比较，每次取出较小的值for(leti=p,j=0,k=0;i
