合并排序与递归承诺

Question

我正在尝试在 JS 中实现基本的归并排序。我正在使用 promises 和 flowtype。但是，当数组被拆分为 2 以下时，我当前的实现永远不会停止递归。有人能告诉我我做错了什么吗？

let inputArr: Array<Number> = [1,2,8,3,2,10,9,7,5];
let mergesortAsync = function(input:Array<Number>) {
  "use strict";
  return new Promise((resolve,reject)=>{
    if(input.length <2 ){
      console.log('reached bottom, bottom: ',input);
      resolve(input);
    }
    var splitPoint:Number = parseInt(input.length/2);
    var left:Array<Number> = input.slice(0,splitPoint);
    var right:Array<Number> = input.slice(splitPoint,input.length);
    var sortedLeft:Array<Number>;
    var sortedRight:Array<Number>;

    mergesortAsync(left).then(sortLeftResult=>{
      sortedLeft = sortLeftResult;
      mergesortAsync(right).then(sortRightResult => {
        sortedRight = sortRightResult;
        console.log('sorted left: ',sortedLeft,' sorted right: ',sortedRight,' input: ',input, 'splitPoint: ',splitPoint);
        mergeAsync(input.slice(),sortedLeft,sortedRight).then(result => {
          resolve(result);
        });
      });
    });
  });
};
let mergeAsync = function(mergeInto: Array<Number>, left: Array<Number>, right: Array<Number>){
  return new Promise((resolve,reject)=>{
    "use strict";
    var mIndex:Number = 0;
    var lIndex:Number = 0;
    var rIndex:Number = 0;
    console.log('Merge start: mergeInto: ',mergeInto, ' left: ',left, ' right: ',right);
    for(mIndex=0; (lIndex< left.length && rIndex<right.length) ;mIndex++){
      if(left[mIndex]<=right[mIndex]){
        mergeInto[mIndex] = left[lIndex];
        lIndex++;
      } else{
        mergeInto[mIndex] = right[rIndex];
        rIndex++;
      }
      console.log('Looping - mIndex: ',mIndex,' rIndex: ',rIndex, ' lIndex: ',lIndex);
    }
    console.log('End Loop - mIndex: ',mIndex,' rIndex: ',rIndex, ' lIndex: ',lIndex);
    while(lIndex<left.length){
      mergeInto[mIndex] = left[lIndex];
      lIndex++;
      mIndex++;
    }
    while(rIndex<right.length){
      mergeInto[mIndex] = right[rIndex];
      rIndex++;
      mIndex++;
    }
    console.log('Merge complete: mergeInto: ',mergeInto, ' left: ',left, ' right: ',right);
    resolve(mergeInto);
  });
};

mergesortAsync(inputArr).then(results => console.log('Sorted result: ',JSON.stringify(result)))
.catch(error => console.log('Error: ',error));

Answer 1

It never stops the recursion when the array is split down below length of 2

是 - 因为 resolve 不是 return，它不会停止您的函数的执行。使用任一

if (input.length < 2) {
    …
} else {
    …
}

或

if (input.length < 2) {
    …
    return;
}
…

合并排序与递归承诺

mergesort with recursive promises

javascript

mergesort

promise