I have been looking around the web for a while and I am wondering if there is a 'stable' defacto implementation of quicksort that is generally used? I can write my own but why reinvent the wheel...
You can easily "stabilize" an unstable sort using a decorate-sort-undecorate pattern
function stableSort(v, f)
{
if (f === undefined) {
f = function(a, b) {
a = ""+a; b = ""+b;
return a < b ? -1 : (a > b ? 1 : 0);
}
}
var dv = [];
for (var i=0; i<v.length; i++) {
dv[i] = [v[i], i];
}
dv.sort(function(a, b){
return f(a[0], b[0]) || (a[1] - b[1]);
});
for (var i=0; i<v.length; i++) {
v[i] = dv[i][0];
}
}
the idea is to add the index as last sorting term so that no two elements are now "the same" and if everything else is the same the original index will be the discriminating factor.