Intrinsic Programming by Erik Schulz

Thinking about Cartesian tree sort some more it seems logical to also use the Cartesian tree as the priority queue since it is already a heap. Performance appears to be the same without the extra memory requirement of an external priority queue.

algorithms.sort.cartesian_tree_erik = function(array, predicate) {
    var length = array.length;
    if (length <= 1) return;
            
    var root = {"parent": null, "value": array[0], "left": null, "right": null};
    var last = root;
    for (var i = 1; i < length; i++) {
        while(last && predicate(last.value, array[i])) {
            last = last.parent;
        }
        if (last) {
            last.right = {"parent": last, "value": array[i], "left": last.right, "right": null};
            last = last.right;
        } else {
            root = {"parent": null, "value": array[i], "left": root, "right": null};
            last = root;
        }
    }
            
    var i = 0;
    while (root) {
        array[i] = root.value;
        i++;

        if (!root.left) {
            root = root.right;
            continue;
        }
                
        if (!root.right) {
            root = root.left;
            continue;
        }

        if (predicate(root.left.value, root.right.value)) {
            var insert = root.left;
            root = root.right;
        } else {
            var insert = root.right;
            root = root.left;
        }
                
        var next = root;
        do {
            if (!next.left) {
                next.left = insert;
                break;
            }
                    
            if (!next.right) {
                next.right = insert;
                break;
            }

            if (predicate(next.left.value, next.right.value)) {
                if (predicate(next.left.value, insert.value)) {
                    var temp = next.left;
                    next.left = insert;
                    insert = temp;
                } else {
                    next = next.left;
                }
            } else {
                if (predicate(next.right.value, insert.value)) {
                    var temp = next.right;
                    next.right = insert;
                    insert = temp;
                } else {
                    next = next.right;
                }      
            }
        } while (true);
    }
};