Tree sort


A tree sort is a sort algorithm that builds a binary search tree from the elements to be sorted, and then traverses the tree so that the elements come out in sorted order. Its typical use is sorting elements online: after each insertion, the set of elements seen so far is available in sorted order.

Efficiency

Adding one item to a binary search tree is on average an process. Adding n items is an process, making tree sorting a 'fast sort' process. Adding an item to an unbalanced binary tree requires time in the worst-case: When the tree resembles a linked list. This results in a worst case of time for this sorting algorithm.
This worst case occurs when the algorithm operates on an already sorted set, or one that is nearly sorted, reversed or nearly reversed. Expected time can however be achieved by shuffling the array, but this does not help for equal items.
The worst-case behaviour can be improved by using a self-balancing binary search tree. Using such a tree, the algorithm has an worst-case performance, thus being degree-optimal for a comparison sort. However, tree sort algorithms require separate memory to be allocated for the tree, as opposed to in-place algorithms such as quicksort or heapsort. On most common platforms, this means that heap memory has to be used, which is a significant performance hit when compared to quicksort and heapsort. When using a splay tree as the binary search tree, the resulting algorithm has the additional property that it is an adaptive sort, meaning that its running time is faster than for inputs that are nearly sorted.

Example

The following tree sort algorithm in pseudocode accepts a collection of comparable items and outputs the items in ascending order:
BinaryTree
BinaryTree:LeftSubTree
Object:Node
BinaryTree:RightSubTree
Insert
searchTree.Node NULL
searchTree.Node item

item searchTree.Node
Insert

Insert
InOrder
searchTree.Node NULL


InOrder
searchTree.Node
InOrder
TreeSort
BinaryTree:searchTree

individualItem items
Insert

InOrder
In a simple functional programming form, the algorithm would look something like this:

data Tree a = Leaf | Node a
insert :: Ord a => a -> Tree a -> Tree a
insert x Leaf = Node Leaf x Leaf
insert x
| x <= y = Node y s
| x > y = Node t y
flatten :: Tree a ->
flatten Leaf =
flatten = flatten t ++ ++ flatten s
treesort :: Ord a => ->
treesort = flatten. foldr insert Leaf

In the above implementation, both the insertion algorithm and the retrieval algorithm have worst-case scenarios.