Javascript Mergesort

A while ago, I couldn’t find any Javascript mergesort implementations, so I wrote one. The nice thing about mergesort is that it is “stable”, id est it retains the previous order of elements with equal value. Therefore it is great for sorting rows in a table on different columns sequentially. Also, the merge() function is handy for merging two sorted arrays into one big sorted array.

Check out Wikipedia for more info on mergesort and other sorting algorithms.

Here it is:

var MergeSorter = function(comparator) {
	var merge = function(a, b)
	{
		var aLen = a.length;
		var bLen = b.length;
	
		if(aLen == 0)
			return b;

		if(bLen == 0)
			return a;

		var i, j, k;
		i = j = k = 0;
		var result = Array();
		while(i < aLen && j < bLen)
		{
			if(comparator.compare(b&#91;j&#93;, a&#91;i&#93;))
				result.push(a&#91;i++&#93;);
			else
				result.push(b&#91;j++&#93;);
		}
		while(i < aLen)
			result.push(a&#91;i++&#93;);
	
		while(j < bLen)
			result.push(b&#91;j++&#93;);
	
		return result;
	};
	return {
		sort: function(a)
		{
			var aLen = a.length;
			if(aLen <= 1)
			{
				return a;
			} else {
				var middle = Math.round(aLen / 2);
				var left = a.slice(0, middle);
				var right = a.slice(middle);
				left = this.sort(left);
				right = this.sort(right);
				var result = merge(left, right);
				return result;
			}

		}
	}
};

var normalComparator = {
	compare: function(n1, n2)
	{
		return n1 >= n2;
	}
};

Here is sample code that makes use of the MergeSorter and does some sanity checks. It could easily be turned into a set of unit tests.

var mockComparator = {
		calls: 0,
		compare: function(n1, n2)
		{
			this.calls++;
			return n1.num >= n2.num;
		}
};

function writeError(str)
{
	document.write('<span style="color: red;">' + str + '</span><br>');
}

var size = 100000;
var ary = new Array(size);
for(var i = 0; i < size; i++)
{
	var num = Math.round(Math.random() * size);
	ary[i] = {num: num, id: i};
}
document.write('<br>');

var start = new Date().getTime();
var myMergeSorter = new MergeSorter(mockComparator);
ary = myMergeSorter.sort(ary);
var stop = new Date().getTime();
var executionTime = stop - start;

document.write('Merge sorting an array with ' + ary.length + ' random integers in it...<br>');
document.write('Execution time: ' + executionTime / 1000 + 's<br>');
document.write('Result length: ' + ary.length + '<br>');
document.write('Comparisons: ' + mockComparator.calls + '<br>');

var ceilLgN = Math.ceil(Math.log(size) / Math.log(2));
var maxExpectedCompares = (size * ceilLgN - Math.pow(2, ceilLgN) + 1);
document.write('Worst case (for this size): ' + maxExpectedCompares + '<br>');
document.write('Theoretical average (for this size): ' + (maxExpectedCompares - 0.2645 * size) + '<br>');

if(ary.length != size)
{
	writeError('Result is not the right size: ' + ary.length);
}

for(var i = 0; i < ary.length; i++)
{
	if(ary[i + 1])
	{
		if(ary[i].num > ary[i + 1].num)
		{
			writeError('Sorting error at index ' + i + '! ' + ary[i].num + ' greater than ' +
				ary[i + 1].num);
			break;
		}
		if(ary[i].num == ary[i + 1].num && ary[i].id > ary[i + 1].id)
		{
			writeError('Stability error at index ' + i + '! ' + ary[i].id + ' greater than ' +
				ary[i + 1].id);
			break;
		}
	}
}

if(mockComparator.calls > maxExpectedCompares)
{
	writeError('Too many comparisons executed!');
}

Edit on December 1, 2010: I modernized the code a bit by making use of object literals, closures, etc. The comparator no longer has to be passed down the recursion. In order to do that with merge() and sort() as top-level functions, the comparator would have to be assigned to a global variable. Also, I added a more thorough example of the usage, with sanity checks.

It is worthwhile to mention that some Javascript implementations, array.sort() is already stable. See, for example, the documentation on sort at the MDC. Since native implementations of sort() have the potential to be much faster, it may be worthwhile to check whether this is the case and if so implement user agent testing to determine whether to use Javascript’s sort, or your own implementation.