归并排序的原理：将两个有序数列整合成一个数列。最简单的方法就是用自顶向下的递归来实现，其实现代码如下，但是在JS中不推荐
function merge1(arr1,arr2) {
var p1=0,p2=0,arr=[];
while ((p1<arr1.length)&&(p2<arr2.length)) {
if (arr1[p1]<arr2[p2]) {
arr.push(arr1[p1++]);
}
else arr.push(arr2[p2++]);
}
return arr.concat(arr1.slice(p1),arr2.slice(p2)); //合并arr1或arr2中未合并的数
}
function mergeSort1(arr) {
if (arr.length<=1) {
return arr
}
var index=Math.floor(arr.length/2);
var arrLeft=arr.slice(0,index);
var arrRight=arr.slice(index);
return merge1(mergeSort1(arrLeft),mergeSort1(arrRight));
}
推荐使用自底向上的迭代循环来代替自顶向下的递归：
一开始由递归改写的版本：
/* 自底向上的归并排序1 */
function merge1(arr1,arr2) {
var p1=0,p2=0,k=0,arr=[];
while ((p1<arr1.length)&&(p2<arr2.length)) {
if (arr1[p1]<arr2[p2]) arr.push(arr1[p1++]);
else arr.push(arr2[p2++]);
}
return arr.concat(arr1.slice(p1),arr2.slice(p2));
}
function mergeSort1(arr) {
var step=1,left,right;
while (step<arr.length) {
left=0;
right=step;
while (right+step<=arr.length) {
var arrTemp=merge1(arr.slice(left,left+step),arr.slice(right,right+step));
for (var index=left,j=0;index<right+step;index++) {
arr[index]=arrTemp[j++]
}
left=right+step;
right=left+step;
}
if (right<arr.length) {
arrTemp=merge1(arr.slice(left,left+step),arr.slice(right,arr.length));
for (var index=left,j=0;index<arr.length;index++) {
arr[index]=arrTemp[j++]
}
}
step*=2;
}
}
由于代码中改写原数组存在重复代码，所以改写版本如下：
/* 自底向上的归并排序2 */
function merge2(arr,startLeft,stopLeft,startRight,stopRight) {
var arrLeft=arr.slice(startLeft,stopLeft),
arrRight=arr.slice(startRight,stopRight);
var p1=0,p2=0,k=startLeft,arrTemp=[];
while ((p1<arrLeft.length)&&(p2<arrRight.length)) {
if (arrLeft[p1]<arrRight[p2]) arrTemp.push(arrLeft[p1++]);
else arrTemp.push(arrRight[p2++]);
}
arrTemp=arrTemp.concat(arrLeft.slice(p1),arrRight.slice(p2));
for (var k=startLeft,j=0;k<stopRight;k++,j++) {
arr[k]=arrTemp[j]
}
}
function mergeSort2(arr) {
var step=1,left,right;
while (step<arr.length) {
left=0;
right=step;
while (right+step<=arr.length) {
merge2(arr,left,left+step,right,right+step);
left=right+step;
right=left+step;
}
if (right<arr.length) merge2(arr,left,left+step,right,arr.length); //往往最后一部分数组末端部位arr.length-1
step*=2;
}
}
可以看出归并排序的时间复杂度为nLogn，其中的Logn为step成指数增长引起的，n可以在merge函数中看出。
