Here is an implementation of the merge sort in JavaScript with an example of use.

To sort an html table I wanted a stable sorting procedure.
This is where I used it.  Click on columns titles to do a sort.  Click again to sort in descending order.
This is the script I did write.  The function lt_or_eq is customized to fit the different data types present in each column.

var desc=false;

function lt_or_eq(obj1, obj2)
{
   return (desc) ? obj1 >= obj2 : obj1 <= obj2;
}

function mergesort(arr)
{
   var left = new Array();
   var right = new Array();
   var len = arr.length;

   if (len <= 1) return arr;

   var middle = Math.floor(len / 2);
   for (var i = 0; i < middle; i++) left.push(arr[i]);
   for (var i = middle; i < len; i++) right.push(arr[i]);

   left = mergesort(left);
   right = mergesort(right);

   return merge(left, right);
}

function merge(left, right)
{
   var retval = new Array();
   while(left.length > 0 && right.length > 0)
   {
      if (lt_or_eq(left[0], right[0])) retval.push(left.shift());
      else retval.push(right.shift());
   }

   if (left.length > 0) return retval.concat(left);
   if (right.length > 0) return retval.concat(right);

   return retval;
}

The code above is correct to sort an array of objects for which the operators >= and <= will give a relevant result.  To sort in descending order, change the value of desc to true.

I found the merge sort algorithm description at en.wikipedia.org.

Home