merge sortのjavascriptが実現しました.

再帰する
前のブログで、jsでquicksortアルゴリズムを実現しました.quicksortアルゴリズムは再帰的呼び出しプロセスです.
再帰的には非常に強力なプログラミング思想であり、様々な言語の中に広く存在しています.特にlispの方言の中では、再帰的に循環操作を実現するために大量に使われています.
もう一冊の小書は「The litter schemer」といいます.プログラムを作った人が再帰的に考える問題です.
本論は上編に続き、再帰思想に対する実践である.よくあるアルゴリズムを学びながら、再帰思想を運用する.
再帰思想を理解しました.以前は難しいと思っていたアルゴリズムも思ったほど難しくないと思いました.
mergsort in javascript

の最も簡単な状況は、2つの要素の配列の順序付けである.

もし2つの配列が順序付けされているなら、この2つの配列を秩序化された配列に再結合するのは比較的容易である.

の混乱した配列は、常に二つの部分に分けられ、また二つの部分に分けられます.一つの部分が二つの要素だけを含むまでは、第1のステップに戻り、二つの要素の配列を並べ替えます.

これは再帰プロセス

である.

function first(l){

  return l[0];

}

function rest(l){

  return l.slice(1);

}



/**   2

 * l1 l2              

 *     l1 l2    ，          

 * */

function mergelist(l1,l2){

  var ret

  if(l1.length == 0){

    ret = l2;

  }else if(l2.length == 0){

    ret = l1;

  }else if(first(l1)>first(l2)){//      

    ret = [].concat(first(l2),

                    mergelist(l1,rest(l2)))

  }else{

    ret = [].concat(first(l1),//        

                    mergelist(l2,rest(l1)))

  }

  return ret;

}



// console.log(mergelist([2,3],[1,4,5]));

// console.log(mergelist([1,4,5],[2,3]));

// --> [ 1, 2, 3, 4, 5 ]



//                         ——  

//                                    

//         divide     

// console.log(mergelist([5],[2]));

// --> [ 2, 5 ]





//   3    

//           

function divide(l){

  var len = l.length

    , mid = Math.floor(len/2);

  return [l.slice(0,mid),l.slice(mid,len)]

}



// console.log(divide([1,4,5,2,3]));

//--> [ [ 1, 4 ], [ 5, 2, 3 ] ]



//     

function mergesort(l1){

  var ab = divide(l1)

    , a = ab[0]

    , b = ab[1];



  if(a.length == 0){

    return b;

  }else if(b.length == 0){

    return a;

  }else if(a.length == 1){

    return [].concat(mergelist(a,mergesort(b)));

  }else if(b.length == 1){

    return [].concat(mergelist(b,mergesort(a)));

  }else{

    return [].concat(mergelist(mergesort(a),

                               mergesort(b)));

  }

}



console.log(mergesort([5,2,3,4]));

console.log(mergesort([5,3,4]));

// console.log(mergesort([1,4,5,2,3]));



//   [].concat     

// [].concat(1,[2,3])   -> [1,2,3]

// [].concat([1],[2,3]) -> [1,2,3]

// [].concat(1,2,3)     -> [1,2,3]