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); } };

## 2 comments:

Very cool. what is the average case complexity time for this Cartesian tree merge?

It has a worst-case and average time complexity of Θ(n log(n)) and a best case of Θ(n) time. It's always Θ(n) memory requirement.

Post a Comment