关于归并算法。。。

Question

最近在参考别的大神的一些实例来写一些基础的算法demo。
在写到归并算法的时候就出现了一点的问题。

function MergeSort(array) {
    var length = array.length;
    if (length <= 1) {
        return array;
    } else {
        var num = Math.ceil(length/2);
        var left = MergeSort(array.slice(0, num));
        var right = MergeSort(array.slice(num, length));
        return merge(left, right);
    }
}

function merge(left, right) {
    console.log(left);
    console.log(right);
    var a = new Array();
    while (left.length > 0 && right.length > 0) {
        if (left[0] <= right[0]) {
            var temp = left.shift();
            a.push(temp);
        } else {
            var temp = right.shift();
            a.push(temp);
        }
    }
    if (left.length > 0) {
        a = a.concat(left);
    }
    if (right.length > 0) {
        a = a.concat(right);
    }
    console.log(a);
    console.log("-----------------------------");
    return a;
}

额，用了webstorm的debug来一步步的查看。但是最后的那个return a返回的 a 是给mergeSort这个函数接收还是到达哪里？搞不懂这个算法的递归步骤， debug的时候 return a 这一步的下一步是mergeSort这个函数的闭括号，然后就是right那一步。为什么啊？

求大神解释下。这个是如何进行递归的。

Answer 1

自荐一篇以前写的文章，http://www.cnblogs.com/zichi/...

如果还不懂，继续提问

Answer 2

    var left = MergeSort(array.slice(0, num));
    var right = MergeSort(array.slice(num, length));
    return merge(left, right);

这三句类似于二叉树的后序遍历
先二分递归将array拆分成length<=1的若干个数组，再逐层归并回来

Answer 3

递归

function sortB(ary){
  if(ary.length<=1){
      return ary[0].constructor==Array?ary[0]:ary;
  }else{
     var tempAry=[];
     for(var i=0;i<ary.length;i=i+2){
         if(ary[i+1]!=undefined){
         tempAry[i/2]=sortIn(ary[i],ary[i+1]);
         }else{
         tempAry[i/2]=ary[i];
         }  

     }
     return  sortB(tempAry);
  }
}
function sortIn(ary1,ary2){
     if(typeof ary1!="object"){
      ary1=[ary1];
     }
      if(typeof ary2!="object"){
      ary2=[ary2];
     }
    var ary=[];
    var i=0,j=0;
  while(i<ary1.length&&j<ary2.length){
         if(ary1[i]<=ary2[j]){
          ary.push(ary1[i]);
          i++;
         }else{
          ary.push(ary2[j]);
          j++;
         }
    }
    if(i<ary1.length){
           for(var m=i;m<ary1.length;m++){
           ary.push(ary1[m]);
           }
    }else{
       for(var m=j;m<ary2.length;m++){
           ary.push(ary2[m]);
           }
    }   
       return ary;
  }

非递归

function sortA(ary){
   while(ary.length>1){
     var tempAry=[];
     for(var i=0;i<ary.length;i=i+2){
         if(ary[i+1]!=undefined){
         tempAry[i/2]=sortIn(ary[i],ary[i+1]);
         }else{
         tempAry[i/2]=ary[i];
         }  

     }
     ary=tempAry;
  }
  return ary[0].constructor==Array?ary[0]:ary;
}

function sortIn(ary1,ary2){
        debugger;
       if(typeof ary1!="object"){
        ary1=[ary1];
       }
        if(typeof ary2!="object"){
        ary2=[ary2];
       }
        var ary=[];
        var i=0,j=0;
    while(i<ary1.length&&j<ary2.length){
         if(ary1[i]<=ary2[j]){
          ary.push(ary1[i]);
          i++;
         }else{
          ary.push(ary2[j]);
          j++;
         }
      }
        if(i<ary1.length){
           for(var m=i;m<ary1.length;m++){
           ary.push(ary1[m]);
           }
        }else{
           for(var m=j;m<ary2.length;m++){
           ary.push(ary2[m]);
           }
        }        
       return ary;
    }