Web Hosting, Free Web Site Builder & Domain Name, Web Hosting Made Easy By Brinkster

MergeSort algorithm

Added By: poxe

Rated:

(4 of 5) by 1.

Rate Snippet: 12345

Description:

The MergeSort algorithm is one of the quicker sort algorithms known. It has a "complexity" of n*log(n), which means that if you need to order some elements, it will take a time defined by n*log(n) where n is the time needed to perform operations on a single element. In some cases it is quicker than the quicksort algorithm, which is known to be the quickest sort known algrithm. It is also about six time faster than the sort method in the Array object of Internet Explorer.

Language: JavaScript

Save to web space
E-mail Link

Code Snippet:

// An example is available at:
// http://www.jargoncode.it/Services/CodeBank/SampleViewer.asp?UID=378685506018519

// This is a private object. You don't need to create instances of it.
function ExtensibleObject(_parms, children)
{
	var i;
	this.child=children;
	this.text=_parms;
}

ExtensibleObject.prototype.GetTypedData=function(data)
{
	var num=new Number(data);
	if(isNaN(Date.parse(data))==false)
		return new Date(Date.parse(data));
	if(isNaN(num)==false)
		return num;
	return data;
 }

// This is a list of ExtensibleObject elements. You will have to create an instance of this object but continue to read the code for now.
function SmartList()
{
	this._vector=[];
}

// This method is used to add elements to the SmartList. The first parameter determine the order. The second parameter can be any type of data you need (strings, numbers, arrays, custom objects or DHTML elements).
SmartList.prototype.Add=function(sortparm, item)
{
	this._vector[this._vector.length]=new ExtensibleObject(sortparm, item);
}

// Get the element at the specified index. You can use it to retrieve elements from the sorted list.
SmartList.prototype.Get=function(index)
{
	return this._vector[index].child;
}

// Used to get the total number of elements. Must be used in conjunction with the Get method.
SmartList.prototype.GetCount=function()
{
	return this._vector.length;
}

// This is the main object. You MUST create an instance of it using this sintax:
// var sorter=new SmartSorter();
// After that you MUST initialize the BaseList property using this sintax:
// sorter.BaseList=new SmartList();
// After that you can add elements to the BaseList object.
// When you have added all elements, call the Sort method to sort elements.
//  The OrderedList property will become the ordered list.
function SmartSorter()
{
	this.tag="";
	this.BaseList=new SmartList();
	this.OrderedList=new SmartList();
}

SmartSorter.prototype.GetTypedData=function(data)
{
	var num=new Number(data);
	if(isNaN(Date.parse(data))==false)
		return new Date(Date.parse(data));
	if(isNaN(num)==false)
		return num;
	return data;
 }

// Begin sort operations.
SmartSorter.prototype.Sort=function()
{
	this.OrderedList._vector=this.MergeSort(this.BaseList._vector);
}

// The core of the algorithm.
SmartSorter.prototype.MergeSort=function(sourcevector)
{
	var FirstHalf=new Array();
	var SecondHalf=new Array();
	var OrderedVector=new Array();

FirstHalf=this.FirstVectorHalf(sourcevector);
	SecondHalf=this.SecondVectorHalf(sourcevector);
	if(FirstHalf.length>1)
		FirstHalf=this.MergeSort(FirstHalf);
	if(SecondHalf.length>1)
		SecondHalf=this.MergeSort(SecondHalf);

OrderedVector=this.MergeVectors(FirstHalf, SecondHalf);
	return OrderedVector;
}

// The core of the algorithm.
SmartSorter.prototype.FirstVectorHalf=function(sourcevector)
{
	var vector1=new Array();
	var i=0;
	var hvl=(sourcevector.length-1)/2;
	for(i=0;i<hvl;i++)
		vector1[i]=sourcevector[i];
	return vector1;
}

// The core of the algorithm.
SmartSorter.prototype.SecondVectorHalf=function(sourcevector)
{
	var vector1=new Array();
	var i=0;
	var c=0;
	var modulus=sourcevector.length % 2;
	var hvl=(sourcevector.length-modulus)/2;
	for(i=hvl;i<sourcevector.length;i++)
		vector1[c++]=sourcevector[i];
	return vector1;
}

// The core of the algorithm.
SmartSorter.prototype.MergeVectors=function(vector1, vector2)
{
	var ResultVector=new Array();
	var c1=0;
	var c2=0;
	var cr=0;

while(c1<vector1.length && c2<vector2.length)
	{
		if(vector1[c1].text<vector2[c2].text || vector1[c1].text==vector2[c2].text)
			ResultVector[cr++]=vector1[c1++];
		else
			ResultVector[cr++]=vector2[c2++];
	}
	//Alcuni elementi dell'array di dimensione più grande potrebbero venire ignorati.
	//Essendo i due vettori in ingresso già ordinati, gli elementi ignorati possono essere accodati senza alterare l'ordinamento.
	if(c1<vector1.length)
		while(c1<vector1.length)
			ResultVector[cr++]=vector1[c1++];
	if(c2<vector2.length)
		while(c2<vector2.length)
			ResultVector[cr++]=vector2[c2++];

return ResultVector;
}