mergesort с рекурсивными обещаниями

Question

Я пытаюсь реализовать базовое объединение в JS. Я использую обещания и поток. Однако моя текущая реализация никогда не останавливает рекурсию, когда массив разбивается ниже длины 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

Он никогда не останавливает рекурсию, когда массив разделяется вниз длиной 2

Да - потому что resolve не return, это не останавливает выполнение вашей функции. Используйте либо

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

или

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