Merge sort (JavaScript)

From LiteratePrograms
Jump to: navigation, search
Other implementations: ACL2 | C | C++ | dc | Erlang | Haskell | Java | JavaScript | Lisp | Oz | Perl | Scheme

This is an implementation of mergesort in Javascript.

<<mergesort.js>>=

merge

mergesort

testing

[edit] Mergesort

The mergesort algorithm works by:

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

msort() takes two indexes, one representing the start of the data to be sorted, and one representing the end of the data to be sorted (but in fact pointed to the element that follows the section of data to be sorted). 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>>=
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(array, begin, begin_right, end);
}

function merge_sort(array)
{
	msort(array, 0, array.length);
}

[edit] Merging

We use in-place merging, which doesn't waste much memory, but can be a little complicated. An alternative method is to create a new array and copying the elements in to it.

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>>=
insert

function merge(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 allready 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;
}

[edit] 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 array=form.unsorted.value.split(/ +/);

	merge_sort(array);

	form.sorted.value=array.join(' ');


}
<<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" value="" />
 </form>
</body>
</html>
Download code
hijacker
hijacker
hijacker
hijacker