Since any heap tree, including Cartesian trees, degrade into sorted linked list when they are fully unbalanced it makes sense to try and unbalance the Cartesian tree. It turns out that a Skew heap works great for this. The following Cartesian skew tree now approaches the speed of quick sort (number of compares) for random data while maintaining linear time for nearly sorted data.

I added a quick sort for comparison.algorithms.sort.cartesian_tree_skew = function(array, predicate, profile) { var swapChildren = function(node) { var temp = node.left; node.left = node.right; node.right = temp; }; var length = array.length; if (length <= 1) return; // parent could be removed with the use of a stack 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; } } 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.right; root = root.left; } else { var insert = root.left; root = root.right; } var next = root; do { if (!next.right) { next.right = insert; break; } if (predicate(next.right.value, insert.value)) { next = next.right; } else { var temp = next.right; next.right = insert; swapChildren(insert); insert = temp; } } while (true); } };