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.

Answer 1

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

Answer 2

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]]