// <<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>>=
	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);
	}

	
//	<<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);
				}
			}
		}

//		<<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;
			}

			
			//<<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;
				}