Quick-sort a linked list?

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;

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.

StackExchange Code Review Q#119265, answer score: 2