Quicksort implemented in javascript

quicksortjs.md

Quicksort in Javascript

Webkit's Array.sort() is implemented in c++ as selectionsort. For some variety (and a better time complexity in big arrays), I wrote up an implementation of quicksort:

Source:

(function(window){

	function quicksort(func){
		var cf = (typeof func!=='function') ? function(a,b){ return a <= b;} : cf;
		return _quickRecurse(this,this.length,cf);

		function _quickRecurse(arr,len,cmp){
			if(len<=1) return arr;
			var piv = arr.splice(len/2,1), l =[],g=[];
			for(var i=0; i < len; i++){
				var c = arr[i];
				if(cmp(c,piv)) l.push(c);
				else g.push(c);
			}
			return _quickrecurse(l,l.length,cmp).concat([piv],_quickrecurse(g,g.length,cmp))
		}
	}

	return window.Array.prototype.quicksort = quicksort;

})(window);

Some notes:

• you can pass in a comparator-- the condition should be a <= b.
• optimized for v8 (based on IO slides & w/ closure compiler)
• adds to Array prototype
• the pivot is the middle element. This isn't totally ideal, but the overhead for choosing a random number..

Compressed:

(function(j){return j.Array.prototype.quicksort=function(a){function b(c,a,d){if(1>=c.length)return c;for(var i=c.splice(a/2,1),e=[],f=[],g=0;g<a;g++){var h=c[g];d(h,i)?e.push(h):f.push(h)}return b(e,e.length,d).concat([i],b(f,f.length,d))}return b(this,this.length,"function"!==typeof a&&(!a||2!==a.arguments.length)?function(a,b){return a<=b}:a)}})(window);