實(shí)現(xiàn)歸并排序

另一種非常常見的中間排序算法是歸并排序。像快速排序一樣，歸并排序也使用一種分而治之的遞歸方法來排序數(shù)組。它利用了這樣一個(gè)事實(shí)，只要每個(gè)排序首先排序，它就比較容易排序兩個(gè)數(shù)組。但是我們只需要一個(gè)數(shù)組作為輸入，那么我們?nèi)绾螐倪@個(gè)數(shù)組中得到兩個(gè)排序的數(shù)組呢？那么我們可以遞歸地將原始輸入分成兩部分，直到我們達(dá)到一個(gè)數(shù)組的基數(shù)大小寫。單項(xiàng)數(shù)組是自然排序的，所以我們可以開始組合。此組合將展開分割原始數(shù)組的遞歸調(diào)用，最終生成所有元素的最終排序數(shù)組。歸并排序的步驟是：

1)將輸入數(shù)組遞歸分割為一半，直到產(chǎn)生只有一個(gè)元素的子數(shù)組。

2)將每個(gè)排序的子數(shù)組合并在一起以產(chǎn)生最終排序的數(shù)組。

歸并排序是一種有效的排序方法，時(shí)間復(fù)雜度為O(nlog(n))。這個(gè)算法是受歡迎的，因?yàn)樗切阅茌^好且相對(duì)容易實(shí)現(xiàn)的。

除此之外，這將是我們?cè)谶@里覆蓋的最后一個(gè)排序算法。然而，在稍后的樹數(shù)據(jù)結(jié)構(gòu)部分中，我們將描述堆排序，另一種在其實(shí)現(xiàn)中需要二進(jìn)制堆的有效排序方法。

var array = [];
(function createArray(size) {
  array.push(+(Math.random() * 100).toFixed(0));
  return (size > 1) ? createArray(size - 1) : undefined;
})(25);


function merge(left,right){
    var result=[];
    while(left.length>0&&right.length>0){
        if(left[0]<right[0]){
            result.push(left.shift());
         }else{
             result.push(right.shift());
         }

        
    }
    return result.concat(left,right);
}
function mergeSort(array) {
  // change code below this line
  if (array.length<=1) {
      return array;
  } 
  var arrayIndex=Math.floor(array.length/2)//選取基準(zhǔn)點(diǎn)
  var arr_left=array.splice(0,arrayIndex);
  var arr_right=array.splice(arrayIndex);


  // change code above this line
  return merge(mergeSort(arr_left),mergeSort(arr_right));
}
mergeSort(array)