归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（pide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序

归并排序是一种非常稳定的排序方法，它的时间复杂度无论是平均，最好，最坏都是NlogN。

归并排序的2个步骤

1. 先拆分，一直拆分到只有一个数

2. 拆分完成后，开始递归合并

拆分过程

从上图可以看出，归并排序会将一个数组进行两两拆分，一直拆分到只有一个数的时候停止拆分。
那么拆分的代码就很简单了，就是得到一个指向中间的指针q，将数组拆分成(start,p)和（p，end）两个部分。

 function pide(p, r){
 return Math.floor( (p + r) / 2 );
 }

合并过程

合并的过程就如上图所示

1. 遍历两组数据

2. 进行对比大小

3. 较小的那个值取出来放在第一个位置

举个例子：

 function merge(A, p, q, r){
 const A1 = A.slice(p, q);
 const A2 = A.slice(q, r);
 
 // 哨兵，往A1和A2里push一个最大值，比如防止A1里的数都比较小，导致第三次遍历某个数组里没有值
 
 A1.push(Number.MAX_SAFE_INTEGER);
 A2.push(Number.MAX_SAFE_INTEGER);
 // 循环做比较，每次取出较小的那个值
 for (let i = p, j = 0, k = 0; i < r; i++) {
 if (A1[j] < A2[k]) {
 A[i] = A1[j];
 j++;
 } else {
 A[i] = A2[k];
 k++;
 }
 }
 }

主程序

主程序就是做递归重复上面的操作了

 function merge_sort(A, p = 0, r) {
 r = r || A.length;
 if (r - p === 1) {
 return;
 }
 const q = pide(p, r);
 merge_sort(A, p, q);
 merge_sort(A, q, r);
 merge(A, p, q, r);
 
 return A;
 }

完整代码

 function pide(p, r) {
 return Math.floor((p + r) / 2);
 }
 
 function merge(A, p, q, r) {
 const A1 = A.slice(p, q);
 const A2 = A.slice(q, r);
 A1.push(Number.MAX_SAFE_INTEGER);
 A2.push(Number.MAX_SAFE_INTEGER);
 
 for (let i = p, j = 0, k = 0; i < r; i++) {
 if (A1[j] < A2[k]) {
 A[i] = A1[j];
 j++;
 } else {
 A[i] = A2[k];
 k++;
 }
 }
 }
 
 function merge_sort(A, p = 0, r) {
 r = r || A.length;
 if (r - p === 1) {
 return;
 }
 const q = pide(p, r);
 merge_sort(A, p, q);
 merge_sort(A, q, r);
 merge(A, p, q, r);
 
 return A;
 }