javascript sort

gistfile1.js

/*
    list: the array
    fn: sort fn
    start: the start index of the sorted range, included
    end: the end index of the sorted range, excluded
        means range: [start, end)
        
    modify the array itself and return nothing
*/

function qsort(list, fn, start, end) {
    fn = fn || function(a, b) {
        return a - b;
    };
    
    start = start || 0;
    end = end || list.length;
    
    var l = end - start;
    
    if(l <= 1) return;
    
    // use the last item as the pivot
    var p = list[end - 1];
    
    // i for iteration, j is the right range's start index
    var i = start, j = start;
    
    for(; i < end - 1; ++i) {
        // if less than pivot
        if(fn(list[i], p) < 0) {
            // if cross into the right range, swap with the first one of right range to put it into the left range
            if(i > j) {
                swap(list, i, j);
            }
            
            // right range move on
            ++j;
        }
    }
    
    // move the pivot between the left range and the right range
    swap(list, j, end - 1);
    
    qsort(list, fn, start, j);
    qsort(list, fn, j + 1, end);
}

function swap(list, i, j) {
    var t = list[i];
    list[i] = list[j];
    list[j] = t;
}

// test cases
var l;

function tassert(l1, l2) {
    console.assert(l1.toString() === l2.toString(), l1 + ' should be ' + l2);
}

function tlog(list, res) {
    qsort(list);
    tassert(list, res);
}

tlog([], []);
tlog([1], [1]);
tlog([1, 2], [1, 2]);
tlog([1, 4, 2, 3], [1, 2, 3, 4]);
tlog([5, 3, 7, 4, 1, 9, 8, 6, 2], [1, 2, 3, 4, 5, 6, 7, 8, 9]);


// max first
function maxFirst(a, b) {
    return b - a;
}

l = [1, 4, 3, 2];
qsort(l, maxFirst);
tassert(l, [4, 3, 2, 1]);

// reverse object by key v
function Obj(v) {
    this.v = v;
}
Obj.prototype.toString = function() {
    return this.v;
};

l = [new Obj(1), new Obj(4), new Obj(3), new Obj(2)];
qsort(l, function(a, b) {
    return b.v - a.v;
});
tassert(l, [new Obj(4), new Obj(3), new Obj(2), new Obj(1)]);




//====== swap without creating another variable
function swap2(a, b) {    
    a = a + b;
    b = a - b;
    a = a - b;
}

/*
swap2(1, 8);
swap2(0, 5);
swap2(3, 4);
*/

gistfile2.js

// sort without modify origin list

function qsort(list) {    
    var l = list.length;
    if(l <= 1) return list;
    
    var pi = Math.floor(l / 2),
        p = list[pi];
        
    var left = [], right = [];
    
    for(var i=0; i<l; i++) {
        if(i == pi) continue;
        
        if(list[i] < p) left.push(list[i]);
        else right.push(list[i]);
    }
    
        
    left = qsort(left);
    right = qsort(right);
    
    return left.concat(p, right);
}


l = [10, 1, 8, 7, 9];

console.log(qsort(l));


console.log(l);
//console.log(qsort(l));