前幾天用c++寫排序算法有點上癮，但是為了雨露均沾，不冷落我的javascript，今天決定用js寫歸并排序。
歸并排序，其中的并字，顧名思義，及將小的東西合并為大的東西；歸則指的遞歸，表明了合并的方法。故而，歸并排序意味著這個算法是用遞歸的方式將小的待排序元素合并為大的有序列的元素。
為了說明這個排序的過程，我先選則一組待排序的元素【5,1,9,0,8,2】；首先現(xiàn)將其劃分成一個個小的元素，即【5】，【1】，【9】，【0】，【8】，【2】。然后按照從小到大的次序兩兩合并【1,5】，【0,9】，【2，8】。繼續(xù)合并【0,1,5,9】，【2,8】，繼續(xù)【0,1,2,5,8,9】。至此就合并完了。
為了書寫出程序，我們需要明白兩點：
1.如何將大的待排序元素劃分成單個元素
2.如何將兩個小的排序好的元素合并為一個排序好的元素
可以這樣形象的理解，要是元素的長度大于1則繼續(xù)遞歸劃分直至其長度等于一，在劃分的時候給其施加合并的函數(shù)，這樣遞歸劃分完成后自然就會按照合并路線遞歸回來。。。本人表述能力有點差，，大家看代碼吧，如果哪里不懂請留言^_

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));