归并排序
这个排序算法是建立在归并操作上的一种有效的排序算法，算法主要采用分治法，归并排序的算法复杂度为O（n*logn），需要一个与数组的长度n一样的额外空间，实现归并排序通常对于一个数组我们对前半部分进行排序，然后进行后半部分进行排序，实现原地归并操作，不过需要额外的空间存储数组。归并排序分为两种，一种是自顶向下的归并排序，一种是自底向上的归并排序。
一、自顶向下的归并排序
把数组元素不断的二分，直到子数组的元素个数为一个，这时子数组必然是有序的，然后将两个有序的序列合并成一个新的有序的序列，两个新的有序序列又可以合并成另一个新的有序序列，以此类推，直到合并成一个有序的数组。
var data=[1,5,3,23,4,67,8];
function merge(data, left, center, right) {
var tmpArr = [];
var mid = center + 1;
var third = left;
var tmp = left;
while (left <= center && mid <= right) {
if (data[left] <= data[mid]) {
tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
while (tmp <= right) {
data[tmp] = tmpArr[tmp++];
}
}
function sort(data, left, right) {
if (left >= right)
return;
var center = parseInt((left + right) / 2);
sort(data,left,center);
sort(data,center+1,right);
merge(data,left,center,right);
console.log(data);
}
sort(data,0,6);
console.log(data);
二、自底向上的归并排序
其实逻辑跟上一个一样，只有sort函数有差别，不过这个不需要递归到最后，直接从一开始就进行比较，通过控制增量解决合并的问题，如果有8个元素，增量为1时有四组合并，增量为2时候，两组合并，最后进行全部合并。
function sort2(data,left,right)
{
var len=data.length;
for (var sz = 1; sz < len; sz *= 2)
{
for (var lo = 0; lo < len; lo += 2 * sz)
{
merge(data, lo, lo+sz-1, min(lo+2*sz-1, len-1));
}
}
}
function min(m,n) {
if(m<=n){
return m;
}else {
return n;
}
}
结果数组
