JavaScript quicksort

Question

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...

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Answer 1

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.

JavaScript quicksort

Sign up