mergesort with recursive promises

Question

I'm trying to implement a basic mergesort in JS. I'm using promises and flowtype. However my current implementation never stops the recursion when the array is split down below length of 2. Can someone tell me what I'm doing wrong?

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

Avoid the [`Promise` constructor antipattern](http://stackoverflow.com/q/23803743/1048572?What-is-the-promise-construction-antipattern-and-how-to-avoid-it)! — Bergi, Dec 20 '16 at 06:06
WTH are you using promises at all? There's nothing asynchronous in your code. — Bergi, Dec 20 '16 at 06:06
There's plenty of mergesort examples all over the web. Or just strip all the promise stuff from yours, it should still work. — Bergi, Dec 20 '16 at 06:16

score 1 · Accepted Answer · answered Dec 20 '16 at 06:10

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

Yes - because resolve is not return, it does not stop the execution of your function. Use either

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

or

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

mergesort with recursive promises

1 Answers1