Merge sort (JavaScript)

From LiteratePrograms

Other implementations: ACL2 | C | C++ | dc | Eiffel | Erlang | Haskell | Java | JavaScript | Lisp | OCaml | Oz | Perl | Prolog | Python | Ruby | Scheme

This is an implementation of mergesort in Javascript.

<<mergesort.js>>=
merge_inplace
mergesort_inplace
testing

Contents 1 Overview 2 In-place Mergesort 3 Merge Sort 4 In-place Merging 5 Merging 6 Testing

Overview

The mergesort algorithm works by:

• Splitting the data in 2 halves
• Sorting each half
• Merging the halves

In-place Mergesort

msort() takes two integers in addition to the array itself:

1. the index of the first element to be sorted
2. 1 + the index of last element to be sorted

For example, to sort an entire array, the integer arguments would be 0 and the length of the array.

The data is split in two parts, and msort() is recursively called on each. The merge() function is applied on the result, making the data completely sorted. If the provided indexes represent a single element or no elements at all, msort() can just return.

<<mergesort_inplace>>=
function msort(array, begin, end)
{
	var size=end-begin;
	if(size<2) return;
	var begin_right=begin+Math.floor(size/2);
	msort(array, begin, begin_right);
	msort(array, begin_right, end);
	merge_inplace(array, begin, begin_right, end);
}
function merge_sort_inplace(array)
{
	msort(array, 0, array.length);
}

Merge Sort

merge_sort() takes 2 arguments: an array to sort and a comparison function to determine the sort order. It recursively calls itself until it calls itself with an array that is either empty or contains a single entry. Those arrays are passed into merge() until they are unified into one new, sorted array. This approach uses more memory, but performs significantly better on large datasets in JavaScript. It also has the advantage of being stable.

<<merge_sort>>=
function merge_sort(array,comparison)
{
	if(array.length < 2)
		return array;
	var middle = Math.ceil(array.length/2);
	return merge(merge_sort(array.slice(0,middle),comparison),
			merge_sort(array.slice(middle),comparison),
			comparison);
}

In-place Merging

Here we use in-place merging, which doesn't use much memory, but can be a little complicated. An alternative method that creates a new array and copies the elements in to it is shown later.

Each element in the left part is compared with the first element in the right part. If it is larger, the right element is copied to the left half, and the old left element is inserted in the correct position in the right half, using insert(). When all left half elements are tested, the complete array is sorted.

<<merge_inplace>>=
insert
function merge_inplace(array, begin, begin_right, end)
{
	for(;begin<begin_right; ++begin) {
		if(array[begin]>array[begin_right]) {
			var v=array[begin];
			array[begin]=array[begin_right];
			insert(array, begin_right, end, v);
		}
	}
}

Inserting an element into the right part is simple. The first element is already copied to the left part, so it can be thrown away. The insert() function moves all elements smaller than the value to be inserted 1 position left. The value to be inserted is then copied to the free position.

<<insert>>=
Array.prototype.swap=function(a, b)
{
	var tmp=this[a];
	this[a]=this[b];
	this[b]=tmp;
}
function insert(array, begin, end, v)
{
	while(begin+1<end && array[begin+1]<v) {
		array.swap(begin, begin+1);
		++begin;
	}
	array[begin]=v;
}

Merging

This merge method destroys temporary arrays and moves their elements into a new array in the sorted order determined by the comparison function and then adds any left over elements that either of the two temporary arrays might have had sine they are not guaranteed to be the same length.

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

Testing

To test the algorithm, we create a simple HTML page with a form containing two edit boxes, one for the unsorted words and one for the result of running merge_sort().

<<testing>>=
function dosort(form)
{
	var inplace_array=form.unsorted.value.split(/ +/);
	var array=form.unsorted.value.split(/ +/);
	merge_sort_inplace(inplace_array);
	array = merge_sort(array,comparison);
	form.sorted_inplace.value=inplace_array.join(' ');
	form.sorted.value = array.join(' ');
}
function comparison(left, right)
{
	if(left == right)
		return 0;
	else if(left < right)
		return -1;
	else
		return 1;
}

<<mergesort.html>>=
<html>
<head>
 <title>Merge sort test</title>
  <script type="text/javascript" src="mergesort.js" >
  </script>
</head>
<body>
 <form id="msform" action="" method="" >
  <input type="text" size="80" name="unsorted" 
   value="Paris London Stockholm Berlin Oslo Rome Madrid Tallinn Amsterdam Dublin" /> <br />
  <input type="button" name="sort" value="Sort" onclick="dosort(this.form)" /> <br />
  <input type="text" size="80" name="sorted_inplace" value="" />
  <input type="text" size="80" name="sorted" value="" />
 </form>
</body>
</html>

Download code