Tree Sort: an online O(n log n) sorting algorithm

mgcadmin 18-09-2021

Sorting: Faster is Better

Tree sort is one of the less discussed sorting algorithms. The three elementary sorting Algorithms bubble sort, insertion sort, and selection sort are all worst case quadratic time algorithms.

Many sorting Algorithms with better than quadratic worst case running times have been discovered, many of which have an average  and worst case complexity of O(n log n). Merge sort, Quicksort, and Heapsort are all well known examples of these faster sorting Algorithms. The subject of this Article is Tree Sort, which is another O(n log n) sorting algorithm.

Tree Sort

Tree sort takes advantage of the ordered property of Binary Search Trees and the fact that an in order traversal of said tree naturally yields the data it contains in sorted ascending order. It works by taking an array and building a binary search tree from the data held in that array. An in-order traversal of the tree is then performed, where the node processing step is placing each nodes data into an array, which yields a sorted array of the original data set.

The code

The following two functions form the meat and potatoes of Tree Sort. Take a look through and then I'll discuss whats going on here.

We need to define a typical binary tree node structure:

struct node {
    int key;
    node* left;
    node* right;
    node(int i) : key(i), left(nullptr), right(nullptr) { } 
};

An inorder traversal places the keys back into the array in sorted order.

void itrinorder(node* h, int a[]) {
    stack<node*> sf;
    int k = 0;
    node* x = h;
    while (x) {
        sf.push(x);
        x = x->left;
    }
    while (!sf.empty()) {
        x = sf.top();
        sf.pop();
        a[k++] = x->key;
        x = x->right;
        while (x) {
            sf.push(x);
            x = x->left;
        }
    }
}

The main function builds the tree from the array, element by element
before calling the recursive inorder function to yield the sorted order:

node* insert(node* h, int k) {
    node* x = h;
    node* p = x;
    while (x != nullptr) {
        p = x;
        x = (k < x->key) ? x->left:x->right;
    }
    x = new node(k);
    if (k < p->key) 
        p->left = x; 
    else 
        p->right = x;
    return h;
}

void treesort(int a[], int l, int r) {
    node* root = new node(a[l]);
    for (int i = l+1; i <= r; i++)
        root = insert(root, a[i]);
    itrinorder(root, a);
}

As you can see, it works by looping through the elements of the unsorted array and inserting each element into a binary search tree.  An in-order depth first traversal of the tree we just created is conducted in order to exploit the property that a binary search tree yields the data sorted in ascending order when subjected to an in-order traversal. Because C inherently passes arrays by reference, thus we don't need an explicit return statement. However, If we so desired, we could return the pointer to the root of the tree we just constructed, facilitating the sorting of future additions to the collection - this is the property which makes it a so called online algorithm.

Lets test tree sort using the follow driver code:

void print(int a[], int n) {
    for (int i = 0; i < n; i++) {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
 
int main() {
    int n = 27;
    int a[n];
    for (int i = 0; i < n; i++) {
        a[i] = rand() % 200;
    }
    print(a, n);
    treesort(a, 0, n - 1);
    print(a, n);
    return 0;
}

Output:
[maxs-MacBook-Pro:~]% ./ts
13 37 42 11 7 69 5 108 127 17 
5 7 11 13 17 37 42 69 108 127 

 

---