Tree sort

Tree sort

Class	Sorting algorithm
Data structure	Array
Worst-case performance	O(n2) (unbalanced) O(n log n) (balanced)
Best-case performance	O(n)
Average performance	O(n log n)
Optimal	Yes, if balanced

A tree sort is a sort algorithm that builds a dumb binary search tree from the keys to be sorted, and then traverses the tree (in-order) so that the keys come out in sorted order. Its typical use is when sorting the elements of a stream from a file. Several other sorts would have to load the elements to a temporary data structure, whereas in a tree sort the act of loading the input into a data structure is sorting it.

Efficiency

Adding one item to a binary search tree is on average an O(log(n)) process, so adding n items is an O(n log(n)) process, making Tree Sort a so-called, 'fast sort'. But adding an item to an unbalanced binary tree needs O(n) time in the worst-case, when the tree resembles a linked list (degenerate tree), causing a worst case of O(n²) for this sorting algorithm. The worst case scenario then is triggered by handing a Tree Sort algorithm an already sorted set. This would make the time needed to insert all elements into the binary tree O(n²). The dominant process in the Tree Sort algorithm is the "insertion" into the binary tree, assuming that the time needed for retrieval is O(n).

The worst-case behaviour can be improved upon by using a self-balancing binary search tree. Using such a tree, the algorithm has an O(n log(n)) worst-case performance, thus being degree-optimal.

Example

In a simple functional programming form, the algorithm (in Haskell) would look something like this:

data Tree a = Leaf | Node (Tree a) a (Tree a)

insert :: Ord a => a -> Tree a -> Tree a
insert x Leaf = Node Leaf x Leaf
insert x (Node t y t') | x <= y = Node (insert x t) y t'
insert x (Node t y t') | x > y = Node t y (insert x t')

flatten :: Tree a -> [a]
flatten Leaf = []
flatten (Node t x t') = flatten t ++ [x] ++ flatten t'

treesort :: Ord a => [a] -> [a]
treesort = flatten . foldr insert Leaf

Mind that in the above example, both the insertion algorithm and the retrieval algorithm have O(n²) worst case scenarios.

External links

• Binary Tree Java Applet and Explanation
• Tree Sort of a Linked List
• Tree Sort in C++