A Different Take on Merge Sort: Binary Search Trees?

mgcadmin 01-11-2024

Sometimes when perusing the literature you come across an interesting algorithm, that while of dubious practical applicability, is none the less of novel interest. This post is about just such an algorithm. I can't be certain, but if i were to hazard a guess about the algorithms which come up the most frequently in my posts, merge sort and binary search trees would be up towards the top. So when I was flipping amongst the exercises section in a chapter on binary search tree's in an algorithms book[1] I've been over countless times, my eyes came upon the following:

- Implement a version of bottom up mergesort based on the join operation in binary search trees: 
  Start by putting keys into N one-node trees, then combine them into pairs to get N/2 two-node trees.
  Combin the two-node trees to get N/4 four node trees, and so forth.

I was intrigued. I've long since been aware of binary tree sort, having covered it in a previous post and of course heapsort, which uses binary trees - albeit not binary search trees. But this was something different: Something new! So, I sat down at my computer and had a go at it, and in todays post I'm going talk about the results.

Merge Two Binary Search Trees

When it comes to merging two binary search trees (while maintaining the search tree property)* there isn't really a "best" way to do it. There are multiple ways to do it, it's just that none of them is particularly easier, or more efficient than any of the other choices. 

You could for example, use the algorithm I presented in a previous post to transform a binary search tree into a sorted linked list. By transforming both tree's into a sorted linked  list, you can then use the linked list merge algorithm to merge the two lists, and then transform the list back into a tree, but for the task we want to accomplish that would be seriously overkill (not to mention inefficient).

Because we know that we are merging even sized tree's we might as well simply traverse one tree, inserting it values into the other, safe in the knowledge that we will never perform more than n/2 insertions.

link put(link h, char info) {
     if (h == nullptr)
        return new node(info);
    if (info < h->info) h->left = put(h->left, info);
    else h->right = put(h->right, info);
    return h;
}

void freetree(link h) {
    if (h != nullptr) {
        freetree(h->left);
        freetree(h->right);
        delete h;
    }
}

link merge(link h, link b) {
    stack<link> sf;
    sf.push(h);
    while (!sf.empty()) {
        link t = sf.top(); sf.pop();
        if (t != nullptr) {
            b = put(b, t->info);
            sf.push(t->right);
            sf.push(t->left);
        }
    }
    freetree(h);
    return b;
}

We can perform this operation in O(1) space complexity instead of O(N) space complexity by using a more complicated insertion algorithm. To accomplish this, we use an insertion algorithm which inserts the value at the root of the tree instead of as a leaf. This is done by first inserting the value as leaf, and then rotating it up to the root once inserted.

link leftRotate(link h) {
    link x = h->right; 
    h->right = x->left; 
    x->left = h;
    return x;
}

link rightRotate(link h) {
    link x = h->left; 
    h->left = x->right; 
    x->right = h;
    return x;
}

link makeRoot(link h, char k) {
    if (h == nullptr) {
        return new node(k);
    }
    if (k < h->info) {
        h->left = makeRoot(h->left, k);
        h = rightRotate(h);
    } else {
        h->right = makeRoot(h->right, k);
        h = leftRotate(h);
    }
    return h;
}

link merge(link a, link b) {
    if (a == nullptr) return b;
    if (b == nullptr) return a; 
    a = makeRoot(a, b->info);
    a->left = merge(b->left, a->left);
    a->right = merge(b->right, a->right);
    delete b;
    return a;
}

Unfortunately, the above algorithm no longer provides a gurantee on how many insertions will be called to perform the merge. Seeing as this is already not an in-place algorithm, this extra complexity may not be worth it. It may depend on you particular situation.

Bottom Up Binary Search Tree Mergesort

If you have read my post on natural mergesort for linked lists then the following code should be seem very familiar, and that's because I am using a similar queue based merge strategy I employed in that algorithm. We want to use a queue because by processing the tree's in first-in first-out order, then we will always merge evenely sized trees. 

We begin by creating a single node bst for element of the input array, using a queue to store them. With the queue populated, we then loop until there is only one item left in the queue. At each iteration we remove two tree's from the queue, merge them, and push the newly created tree to the back of the queue. 

void inorder(link h, char a[], int& n) {
    if (h != nullptr) {
        inorder(h->left, a, n);
        a[n++] = h->info;
        inorder(h->right, a, n);
    }
}

void sort(char a[], int n) {
    queue<link> fq;
    for (int i = 0; i < n; i++) {
        fq.push(new node(a[i]));
    }
    while (fq.size() > 1) {
        link a = fq.front(); 
        fq.pop();
        link b = fq.front(); 
        fq.pop();
        fq.push(merge(a, b));
    }
    int t = 0;
    inorder(fq.front(), a, t);
}

When our loop terminates the queue will contain our complete binary search tree. An inorder traversal of the tree is then used to place the elements into the sorted position in the array.

And so there you have it: bottom up binary search tree-based merge sort. As I said at the beginning of the post: it is of dubious practical applicability. I can't really think of a scenario where this would be the best way to go about sorting a collection of values. Sometimes though, we can program just for the sake of programming: because it's enjoyable. Anway, thats what I have for today, so until next time Happy Hacking!

---