Quick-sort a linked list?

Question

I have a little project where i am implementing an immutable linked-list (not only...) based on a pair-structure like the LISP cons-cell.

The linked list works well and is basically wrapping two variables in a closure in an object, the variables are "head" and "rest" (think LISP´s car and cdr). I have also added some useful functions like map, fold, forEach, merge, reverse and sort among others.

All work well except for sort. As it only works with the default compare-function. I know that the reason is of how i append the list back together after a comparison.

Anyone has a better idea of how this might be done? merge-sort? Also suggestions on other parts of the project are welcome! :-)

var list = function (arr) {

    var listBuilder = function (arr, i) {
        if (i + 1 === arr.length)
            return pair(arr[i], nil);
        else
            return pair(arr[i], listBuilder(arr, i + 1));
    };

    return arr.length > 0 ? listBuilder(arr, 0) : nil;
};

var pair = function (a, b) {
    var cons = function (a, b) {
        var p = function (p) { //base closure to hold the data
            return p ? a : b;
        };        
        p.head = function () {
            return this(true);
        };
        p.rest = function () {
            return this(false);
        };
        p.equal = function (a) {
            return this === a;
        };
        p.toString = function () {
            return '( ' + p.head() + ' , ' + p.rest() + ' )';
        };
        p.len = function () {
            if(nil.equal(p))
                return 0;
            else
                return nil.equal(p.rest()) ? 1 : 1 + p.rest().len();
        };
        p.get = function (i) {
            if(i <= 0){
                return p.head();
            }else if(nil.equal(p.rest())){
                return nil;
            }else
                return p.rest().get(i - 1);
        };
        p.append = function(l) {
            if(nil.equal(p))
                return l;            
            if(nil.equal(p.rest()))
                return pair(p.head(),l);
            else
                return pair(p.head(),p.rest().append(l));                
        }
        p.map = function (fn) {
            return p.merge(fn, pair);
        };
        p.fold = function (fn) {
            return p.merge(function (e) {
                return e;
            }, fn);
        }
        p.forEach = function (fn) {
            if (!nil.equal(p)) {
                fn(p.head());
                p.rest().forEach(fn);
            }
        };
        p.merge = function (modifierFn, concatFn) {
            if(nil.equal(p))
                return nil;
            else if (nil.equal(p.rest()))
                return modifierFn(p.head());
            else
                return concatFn(modifierFn(p.head()), p.rest().merge(modifierFn, concatFn));
        };
        p.reverse = function () {            
            if (nil.equal(p.rest()))
                return p;
            else
                return p.rest().reverse().append( list([p.head()]) );
        };
        p.sort = function(cmp){ //quick-sort
            var pivot = p.head();            
            var left=nil,right=nil;
            cmp = cmp === undefined ? function(a,b){return a < b;}: cmp; //defaults to numerical less then 
            var partion = function(l){
                if(cmp(l.head(), pivot))
                    left = pair(l.head(),left);
                else
                    right = pair(l.head(),right);    
                if(!nil.equal(l.rest())) 
                    partion(l.rest()); 
            };            
            if(!nil.equal(p) && !nil.equal(p.rest())){
                partion(p.rest());    
                return left.sort().append(pair(pivot,nil)).append(right.sort());                        
            }else{
                return p;
            }
        };
        return p;
    };
    return cons(a, b);
};

var nil = pair(null, null);
nil.toString = function () {
    return 'nil';
};

//uses cases
var l = list([213, 342, 654, 543, 213, 321, 54365, 564, 3221, 45, 7, 8, 53, 6542, 24, 8, 523, 543, 984]);
var append = function(a,b){ return a+ ' ' +b;};
alert(l.sort().reverse().fold(append));

Answer 1

The way quick sort is defined (requiring random access) it cannot be efficient for linked lists (especially immutable ones).

I recommend a recursive implementation of merge sort. It will be clear and concise. It should also be relatively efficient.