### Beating Quick Sort - Cartesian Tree Merge

Wednesday, July 7, 2010 by gradbot

After looking at skew heap, merge sort and Cartesian tree, I figured there has to be a way to combine all three. My idea is to start with a cartesian tree, take its root as the first element and then merge its leafs in a way that skews them to the right. Children swapping is employed to keep the tree shallow. The number of comparisons required for this sort is consistently less than quick sort. I also changed the Cartesian tree generator to use a stack instead of a parent node to save memory.

A second test with partially sorted data.

```algorithms.sort.cartesian_tree_merge = function(array, predicate) {
var length = array.length;
if (length <= 1) return;

var root = {"value": array[0], "left": null, "right": null};
var last = root;
var stack = [];

for (var i = 1; i < length; i++) {
while(!predicate(last.value, array[i])) {
if (stack.length) {
last = stack.pop();
} else {
last = null;
break;
}
}
if (last) {
last.right = {"value": array[i], "left": last.right, "right": null};
stack.push(last);
last = last.right;
} else {
root = {"value": array[i], "left": root, "right": null};
last = root;
stack.push(last);
}
}

var swapChildren = function(node) {
var temp = node.left;
node.left = node.right;
node.right = temp;
};

var merge = function(left, right) {
if (!left) {
return right;
}

if (!right) {
return left;
}

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

swapChildren(next);
next.right = merge(insert, next.right);
return next;
};

i = 0;
while (root) {
array[i] = root.value;
i++;
root = merge(root.left, root.right);
}
};
```

Filed under , , , having