前几天用c++写排序算法有点上瘾，但是为了雨露均沾，不冷落我的javascript，今天决定用js写归并排序。
归并排序，其中的并字，顾名思义，及将小的东西合并为大的东西；归则指的递归，表明了合并的方法。故而，归并排序意味着这个算法是用递归的方式将小的待排序元素合并为大的有序列的元素。
为了说明这个排序的过程，我先选则一组待排序的元素【5,1,9,0,8,2】；首先现将其划分成一个个小的元素，即【5】，【1】，【9】，【0】，【8】，【2】。然后按照从小到大的次序两两合并【1,5】，【0,9】，【2，8】。继续合并【0,1,5,9】，【2,8】，继续【0,1,2,5,8,9】。至此就合并完了。
为了书写出程序，我们需要明白两点：
1.如何将大的待排序元素划分成单个元素
2.如何将两个小的排序好的元素合并为一个排序好的元素
可以这样形象的理解，要是元素的长度大于1则继续递归划分直至其长度等于一，在划分的时候给其施加合并的函数，这样递归划分完成后自然就会按照合并路线递归回来。。。本人表述能力有点差，，大家看代码吧，如果哪里不懂请留言_
var array = [5,1,9,0,8,2,7,3,6,4];
var merge_sort = function(array){
var length = array.length;
if(length ===1 )return array;
var mid = Math.floor(length/2),
left = array.slice(0,mid),
right = array.slice(mid,length);
return merge(merge_sort(left), merge_sort(right));
}
var merge = function(left, right){
var result = [],
il = 0,
ir = 0;
while( il < left.length && ir < right.length){
if(left[il] < right[ir]){
result.push(left[il++]);
}else{
result.push(right[ir++])
}
}
while(il<left.length){
result.push(left[il++]);
}
while(ir<left.length){
result.push(right[ir++]);
}
console.log(result);
return result;
}
console.log(merge_sort(array));
