var smallFileSize = 8;

function qSort(sArray,cFunc,left,right) {
	if(sArray && sArray.length && sArray.length > 1)
		(sArray.length > smallFileSize)?quickSort(sArray, ((typeof(cFunc)=="function")?cFunc:simpleCFunc) ,(left?left:0), (right?right:sArray.length-1)):insertionSort(sArray, ((typeof(cFunc)=="function")?cFunc:simpleCFunc), (left?left:0), (right?right:sArray.length-1));
}

function quickSort(sArray,cFunc,left,right) {
	var lPtr = left;
	var rPtr = right;
	var index;
	var qsStack = new Stack();
	qsStack.push(left);
	qsStack.push(right);
	do
		if(rPtr-lPtr > smallFileSize) {
			index = partition(sArray,cFunc,lPtr,rPtr);
			if((index-lPtr)>(rPtr-index)) {
				qsStack.push(lPtr);
				qsStack.push(index-1);
				lPtr = index+1;
			} else {
				qsStack.push(index+1);
				qsStack.push(rPtr);
				rPtr = index-1;
			}
		} else {
			rPtr = qsStack.pop();
			lPtr = qsStack.pop();
		}
	while(!qsStack.isEmpty());
	insertionSort(sArray,cFunc,left,right);
}

function partition(sArray,cFunc,left,right) {
	var lPtr = left-1;
	var rPtr = right;
	var tValue = sArray[lPtr + Math.floor((rPtr - lPtr)/2)];
	sArray[lPtr + Math.floor((rPtr - lPtr)/2)] = sArray[rPtr];
	sArray[rPtr] = tValue;
	var cValue = sArray[rPtr];

	do {
		do
			lPtr++;
		while(cFunc(sArray[lPtr],cValue) < 0 && lPtr<right);
		do
			rPtr--;
		while(cFunc(sArray[rPtr],cValue) > 0 && rPtr>left);
		tValue = sArray[lPtr];
		sArray[lPtr] = sArray[rPtr];
		sArray[rPtr] = tValue;
	} while(rPtr > lPtr);
	sArray[rPtr] = sArray[lPtr];
	sArray[lPtr]  = cValue;
	sArray[right] = tValue;
	return lPtr;
}

function simpleCFunc(a,b) {
	if(a<b)
		return -1;
	else if(a>b)
		return 1;
	else
		return 0;
}

function Stack() {
	this.data = new Array();
	this.pointer = -1;
}
new Stack();

Stack.prototype.push = function(value) {
	this.data[++this.pointer] = value;
};

Stack.prototype.pop = function(value) {	
	return (this.pointer==-1?null:this.data[this.pointer--]);
};

Stack.prototype.isEmpty = function() { return (this.pointer==-1);};

function insertionSort(sArray,cFunc,left,right) {
	var cIndex;
	var tValue;
	var cValue;
	for(var i = left+1; i<=right; i++)	{
		cValue = sArray[i];
		cIndex = i;
		while(cIndex > left && cFunc(sArray[cIndex-1],cValue) == 1) {
			sArray[cIndex] = sArray[cIndex-1];
			cIndex--;
		}
		sArray[cIndex] = cValue;
	}
}