sha.nnoncarey.com/blog

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:

function mergesort(a,f)
{
	var alength = a.length;
	if(alength <= 1)
		return a;
	else
	{
		var middle = Math.round(alength / 2);
		var left = new Array(middle);
		var right = new Array(alength - middle);
		var result = new Array(alength);
		left = a.slice(0, middle);
		right = a.slice(middle, alength);
		left = mergesort(left, f);
		right = mergesort(right, f);
		result = merge(left, right, f);
		return result;
	}
}

function merge(a, b, f)
{
	var alength = a.length;
	var blength = b.length;
	var result = Array();
	var i, j, k;
	i = j = k = 0;
	if(alength == 0)
		return b;
	if(blength == 0)
		return a;
	while(i < alength && j < blength)
	{
		if(f(b[j], a[i]))
			result.push(a[i++]);
		else
			result.push(b[j++]);
	}
	while(i < alength)
		result.push(a[i++]);
	while(j < blength)
		result.push(b[j++]);
	return result;
}

The "f" argument is a comparison function that you provide. Here is a sample comparison function to get you started:

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