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;
        if (last) {
            last.right = {"value": array[i], "left": last.right, "right": null};
            last = last.right;
        } else {
            root = {"value": array[i], "left": root, "right": null};
            last = root;

    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;
        next.right = merge(insert, next.right);
        return next;

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

Filed under , , , having  


Brad said...

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

gradbot said...

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.