Javascript implementation of the inversion-counting with merge-sort algorithm

Question

i am trying to implement the inversion-counting using merge sort algorithm in javascript. I found description and pseudo-code on this site. My implementation looks like this:

var mergeAndCount, sortAndCount;

/*
the merging routine
@param List1 the first list to be merged
@param List2 the second list to be merged
*/

mergeAndCount = function(List1, List2) {
  var count, outputList;
  outputList = [];
  count = 0;
  while (List1.length > 0 || List2.length > 0) {
    outputList.push(Math.min(List1[0], List2[0]));
    if (List2[0] < List1[0]) {
      count += List1.length;
      List2.shift();
    } else {
      List1.shift();
    }
  }

  outputList = outputList.concat(List1.concat(List2));
  return {
    'count': count,
    'list': outputList
  };
};

/*
count inversion algorithm
@param List the sequence to be sorted
*/
sortAndCount = function(List) {
  var List1, List2, mergeOut, output1, output2;
  if (List.length < 2) {
    return {
      'count': 0,
      'list': List
    };
  } else {
    List1 = List.splice(0, List.length / 2);
    List2 = List;
    output1 = sortAndCount(List1);
    output2 = sortAndCount(List2);
    mergeOut = mergeAndCount(List1, List2);
    return {
      'count': output1.count + output2.count + mergeOut.count,
      'list': mergeOut.list
    };
  }
};

I wanted to test it on Jsfiddle here, but it crashes (too much memory used). Somehow it works for the inupt [1, 3, 2] but not for other. I am not sure what is going wrong, if my implementation or the original pseudocode is false.

Tibos · Accepted Answer · 2013-11-19T16:49:42.067

Error 1 : infinite loop

The while goes on for a very long time when it starts to compare numbers with undefined. If List1.length is 0, the comparison List2[0] < List1[0] will always be false, resulting in List1.shift() which changes nothing.

Replace:

while (List1.length > 0 || List2.length > 0) {

With:

while (List1.length > 0 && List2.length > 0) {

Error 2 : manipulating arrays

You alter the arrays and then use what you expect to be their initial values. At the begining of each function you should copy the arrays (using slice is the fastest way).

Error 3 : ignoring output of sortAndCount

Replace:

mergeOut = mergeAndCount(List1, List2);

With:

mergeOut = mergeAndCount(output1.list, output2.list);

Correct solution:

var mergeAndCount, sortAndCount;

/*
the merging routine
@param List1 the first list to be merged
@param List2 the second list to be merged
*/

mergeAndCount = function(List1, List2) {
  List1 = List1.slice();
  List2 = List2.slice();
  var count = 0;
  var outputList = [];

  while (List1.length > 0 && List2.length > 0) {
    outputList.push(Math.min(List1[0], List2[0]));
    if (List2[0] < List1[0]) {
      count += List1.length;
      List2.shift();
    } else {
      List1.shift();
    }
  }
  outputList = outputList.concat(List1.concat(List2));
  return {
    'count': count,
    'list': outputList
  };
};

/*
count inversion algorithm
@param List the sequence to be sorted
*/
sortAndCount = function(List) {
  List = List.slice();
  var List1, List2, mergeOut, output1, output2;
  if (List.length < 2) {
    return {
      'count': 0,
      'list': List
    };
  } else {
    List1 = List.splice(0, Math.floor(List.length / 2));
    List2 = List;
    output1 = sortAndCount(List1);
    output2 = sortAndCount(List2);
    mergeOut = mergeAndCount(output1.list, output2.list);    
    return {
      'count': output1.count + output2.count + mergeOut.count,
      'list': mergeOut.list
    };
  }
};

console.clear();
var r = sortAndCount([1,3,4,2]);
console.log('RESULT',r.list);

DEMO: http://jsbin.com/UgUYocu/2/edit

Thanks, that was wrong for sure. Now it does not freeze, but it also does not work. It does not return sorted array and it gives wrong number of inversions. I also looked at this example http://stackoverflow.com/questions/337664/counting-inversions-in-an-array, there is no example in javascript but one in Python. Now I am not sure how the mergeOut = mergeAndCount(..., ...) call should look like. According to the Python example should it be mergeOut = mergeAndCount(output1.list, output1.list). On the page where I took the description from is something different. — karlitos, Nov 19 '13 at 16:34
Here is an implementation of the Python code in coffeescript http://jsfiddle.net/jgQ4f/6/ which does not crash but also does not give right results. I fell really stupid. — karlitos, Nov 19 '13 at 16:37
I thank you very much! The Error 3 was initially caused by the false description on the site of the Thailand university. I saw it in the Python code and thought that this could be an error. And the Error 2 ... Javascript is still new to me have to think about it a little bit. — karlitos, Nov 19 '13 at 20:24
Can you please explain error 2 again?Like why do we need a copy — Eminem347, Jul 23 '17 at 13:56

georg · Answer 2 · 2013-11-20T10:19:31.450

As pointed out, the problem was || instead of &&. Here's an implementation that seems to work (to make things interesting, it returns a list of inversions instead of simply counting them):

sort_and_count = function(L) {
    if (L.length < 2)
        return [[], L];
    var m = L.length >> 1;
    var na = sort_and_count(L.slice(0, m));
    var nb = sort_and_count(L.slice(m));
    var nc = merge_and_count(na[1], nb[1]);
    return [[].concat(na[0], nb[0], nc[0]), nc[1]];
}

merge_and_count = function(a, b) {
    var inv = [], c = [];

    while(a.length && b.length) {
        if(b[0] < a[0]) {
            a.forEach(function(x) { inv.push([x, b[0]])});
            c.push(b.shift());
        } else {
            c.push(a.shift());
        }
    }
    return [inv, c.concat(a, b)];
}

nn = sort_and_count([2, 4, 1, 3, 5])
// [[[2,1],[4,1],[4,3]],[1,2,3,4,5]]

For completeness, here's the quadratic algorithm:

inversions = function(L) {
    return L.reduce(function(lst, a, n, self) {
        return self.slice(n).filter(function(b) {
            return b < a;
        }).map(function(b) {
            return [a, b];
        }).concat(lst);
    }, []);
}

inversions([2, 4, 1, 3, 5])
// [[4,1],[4,3],[2,1]]

Thank you for the alternate code! I am developping a edge minimization algorithm for bipartite graphs, so I really need to know only the number of inversions (corresponds to the number of edge crossings) — karlitos, Nov 19 '13 at 20:26

Javascript implementation of the inversion-counting with merge-sort algorithm

2 Answers2

Linked