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