By "fastest", I mean runs with the best time on most/all popular web browsers. For explicitness lets say the latest and second latest version of IE, FF, Chrome and Safari.
By "integer", I mean a 32bit signed integer.
Currently I'm under the impression that Radix Sort is the fastest algorithm for this job. I've created a small benchmark page which you can insert your implementation (of whatever sorting algorithm you think is faster) into for testing.
I am * not * looking for micro-optimizations (yet) like loop unrolling, smaller variable names (JS minimization), etc.
I am * not * interested in theories about sorting or personal anecdotes regarding your experiences with sorting.
The use-case I'm interested in is arrays with varying lengths from 50,000 to ~2,000,000.
I'd like fast running implementations of sorting algorithms, in the hopes of finding a definitive answer to my question.
I'm open to interesting solutions like spawning multiple browser windows and creating a sort of multi-threaded approach (and at which array length threshold that approach would tend to run faster).
<html>
<head>
<script type="text/javascript">
var _radixSort_0 = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
function radixSort(intArr) {
var cpy = new Array(intArr.length);
var c4 = [].concat(_radixSort_0);
var c3 = [].concat(_radixSort_0);
var c2 = [].concat(_radixSort_0);
var c1 = [].concat(_radixSort_0);
var o4 = 0; var t4;
var o3 = 0; var t3;
var o2 = 0; var t2;
var o1 = 0; var t1;
// get counts
for(var x=0; x<intArr.length; x++) {
t4 = intArr[x] & 0xFF;
t3 = (intArr[x] >> 8) & 0xFF;
t2 = (intArr[x] >> 16) & 0xFF;
t1 = (intArr[x] >> 24) & 0xFF ^ 0x80;
c4[t4]++;
c3[t3]++;
c2[t2]++;
c1[t1]++;
}
// transform counts to pointers
for (var x=0; x<256; x++) {
t4 = o4 + c4[x];
t3 = o3 + c3[x];
t2 = o2 + c2[x];
t1 = o1 + c1[x];
c4[x] = o4;
c3[x] = o3;
c2[x] = o2;
c1[x] = o1;
o4 = t4;
o3 = t3;
o2 = t2;
o1 = t1;
}
// sort array
for(var x=0; x<intArr.length; x++) {
t4 = intArr[x] & 0xFF;
cpy[c4[t4]] = intArr[x];
c4[t4]++;
}
for(var x=0; x<intArr.length; x++) {
t3 = (cpy[x] >> 8) & 0xFF;
intArr[c3[t3]] = cpy[x];
c3[t3]++;
}
for(var x=0; x<intArr.length; x++) {
t2 = (intArr[x] >> 16) & 0xFF;
cpy[c2[t2]] = intArr[x];
c2[t2]++;
}
for(var x=0; x<intArr.length; x++) {
t1 = (cpy[x] >> 24) & 0xFF ^ 0x80;
intArr[c1[t1]] = cpy[x];
c1[t1]++;
}
return intArr;
}
function quickSort(arr)
{
if (arr.length == 0) return [];
// setup
var left = new Array();
var right = new Array();
var pivot = arr[0];
// quick sort
for (var i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// recurse
return quickSort(left).concat(pivot, quickSort(right));
}
function defaultSort(intArr) {
return intArr.sort(function(a,b){return a-b;});
}
function bench(func, len) {
var test = [];
for(var x=0; x<len; x++) {
test[x] = Math.floor(Math.random()*2000000000) - 1000000000;
}
var s = (new Date()).getTime();
test = func(test);
s = (new Date()).getTime() - s;
document.getElementById('outp').innerHTML += '<br/>' + /(function )([a-z0-9]+)/i.exec(func.toString())[2] + ': ' + s;
for(var x=0; x<len-1; x++) {
if(test[x] > test[x+1]) {
alert('error');
break;
}
}
}
</script>
</head>
<body>
<input type="text" id="lng" value="50000" />
<br/>
<input type="button" value="Radix Sort" onclick="bench(radixSort, parseInt(document.getElementById('lng').value));" />
<input type="button" value="Quick Sort" onclick="bench(quickSort, parseInt(document.getElementById('lng').value));" />
<input type="button" value="Array.Sort" onclick="bench(defaultSort, parseInt(document.getElementById('lng').value));" />
<br/>
<div id="outp" />
</body>
</html>
- edit * For even more clarity
- I am looking for JS implementations (actual JS that runs and is testable).
- I'm well aware that an algorithm of O(n) will likely win (or a well implemented multi-threaded O(n log n) algorithm).
- The benchmarking HTML above is so anyone can easily plug an algorithm in, it's not inferring that those are the ONLY algorithms or that Quick Sort is some how competitive to Radix Sort in this instance.
