mergesortを使用した反転のカウント - javacript

Question

次のコードは、配列内の逆位の数スタックエラー、RangeError：基本ケースが定義されている場合でも、最大呼び出しスタックサイズを超えてしまうまで、常に再帰的にサブ問題に分割されます。ここで問題になる可能性のあるもの

function mergeSort(arr) { 
    var n = arr.length; 
    var l=0,h=n-1; 
    if (l<h) { 
     var m=findMid(l,h); 
     var leftArr=arr.slice(l,m); 
     var rightArr=arr.slice(m,n); 
     var invCount = mergeSort(leftArr)+mergeSort(rightArr); 
     invCount += merge(leftArr,rightArr,n); 
    } 
    return invCount; 
} 

function merge(a, b,n) { 
    var i=0,j=0,m=[]; 
    var splitInv=0; 
    for(var k=0;k<n;k++) { 
     if(a[i]<b[j]) m[k]=a[i++]; 
     else if (b[j]<a[i]){ 
      m[k]=b[j++]; 
      splitInv+=n-i; 
     } 
    } 
    return splitInv; 
} 
function findMid(l, r) { 
    var m = Math.floor((l + r)/2); 
    return m; 
} 

私は別の方法でベースケースを処理するために上記のコードを変更しました。以下のロジックが正しいです：

function mergeSort(arr) { 
    var n = arr.length; 
    var l=0,h=n-1; 
    var invCount=0; 
    if(n<=2) { 
     return merge(arr[0],arr[1],n); 
    }else{ 
     var m=Math.floor(n/2); 
     var leftArr=arr.slice(l,m); 
     var rightArr=arr.slice(m); 
     invCount += mergeSort(leftArr)+mergeSort(rightArr); 
    } 
    return invCount; 
} 

function merge(a, b,n) { 
    var i=0,j=0,m=[]; 
    var splitInv=0; 
    if(typeof b=="undefined") { 
     return 0; 
    } 
    for(var k=0;k<n;k++) { 
     if(a[i]<b[j]) m[k]=a[i++]; 
     else if (b[j]<a[i]){ 
      m[k]=b[j++]; 
      splitInv+=n-i; 
     } 
    } 
    return splitInv; 
} 

Answer 1

は例外RangeErrorが原因mergeSortにあまりにも多くの再帰呼び出しに来ています。 のサイズについてarr のサイズrightArrは、のままです。 代わりの var rightArr=arr.slice(m,n); あなたはここに掲載 var rightArr=arr.slice(m+1,n);

Answer 2

同じ質問、Javascript implementation of the inversion-counting with merge-sort algorithmを行うことができます。これはあなたが必要とするすべてを記述します。