Counting inversions using mergesort - javascript

Question

The following code counts the no. of inversions in an array. It is always recursively getting divided into sub-problems until the stack error, RangeError: Maximum call stack size exceeded occurs even when the base case is defined. What could be the issue here

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

I had modified the above code to handle the base cases in a different way. Is the following logic correct:

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

Your `merge()` function is written to take **3** parameters, but you're only passing **2**. — Pointy, Jun 19 '16 at 14:08
the code is getting exec prop, but as the base case handling is like for 1 elem, returning 0, then the whole result comes 0, whatever be the case — Shyam R, Jun 19 '16 at 15:24
Well, the code is not implementing merge sort. The outcome is not sorted, as the `merge` function should be called on larger array chunks as well, and take offsets as arguments, not values. Also `a[i]` will be undefined in your function, as you pass `a` as a primitive value, not an array. I suggest you read about mergesort and do a correct implementation first (the code is available on wikipedia). — trincot, Jun 19 '16 at 15:33
this implementation is not for sorting, its for finding inversions by using merge sort logic. I mean i am not interested in sorting the array as a priority — Shyam R, Jun 19 '16 at 15:45

Paritosh · Answer 1 · 2016-06-19T15:13:26.813

1

RangeError is coming due to too much recursive call to mergeSort. For the size of arr 2 size of rightArr will remain 2. Instead of var rightArr=arr.slice(m,n); You may do var rightArr=arr.slice(m+1,n);

edited Jun 19 '16 at 15:13

answered Jun 19 '16 at 14:42

Paritosh

505
5
13

slice(from,to), here 'to' index is not sliced. its from to (to-1) which comes as a result. So to get the m elem, we need it in the right array – Shyam R Jun 19 '16 at 14:53
Right. So you may do one thing, var leftArr=arr.slice(l,m+1); and var rightArr=arr.slice(m+1,n); or instead of doing these you may return Math.floor((l + r+1) / 2); from your findMid function. – Paritosh Jun 19 '16 at 15:08
i handled it in a different way. I have written the modified code in the second snippet. But the issue is now inv counts are not counted properly – Shyam R Jun 19 '16 at 15:17

score 1 · Answer 2 · edited May 23 '17 at 12:22

1

Same question posted here, Javascript implementation of the inversion-counting with merge-sort algorithm. This describes everything that you need.

edited May 23 '17 at 12:22

Community

1
1

answered Jul 14 '16 at 10:06

pTM

21
2

Counting inversions using mergesort - javascript

2 Answers2