|Worst case performance||
O(n2) (unbalanced)O(n log n) (balanced)
|Best case performance||O(n)|
|Average case performance||O(n log n)|
A tree sort is a sort algorithm that builds a 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.
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(n2) 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(n2). 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.
The following tree sort algorithm in pseudocode accepts an array of comparable items and prints them to the screen in ascending order:
STRUCTURE BinaryTree BinaryTree:LeftSubTree Object:Node BinaryTree:RightSubTree END STRUCTURE PROCEDURE Insert(BinaryTree:searchTree, Object:item) IF searchTree IS NULL THEN SET searchTree.Node TO item ELSE IF item IS LESS THAN searchTree.Node THEN Insert(searchTree.LeftSubTree, item) ELSE Insert(searchTree.RightSubTree, item) END IF END IF END PROCEDURE PROCEDURE InOrder(BinaryTree:searchTree) IF searchTree IS NULL THEN EXIT PROCEDURE ELSE InOrder(searchTree.LeftSubTree) PRINT searchTree.Node InOrder(searchTree.RightSubTree) END IF END PROCEDURE PROCEDURE TreeSort(Array:items) BinaryTree:searchTree FOR EACH individualItem IN items Insert(searchTree, individualItem) END FOR InOrder(searchTree) END PROCEDURE
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 s) | x <= y = Node (insert x t) y s insert x (Node t y s) | x > y = Node t y (insert x s) flatten :: Tree a -> [a] flatten Leaf =  flatten (Node t x s) = flatten t ++ [x] ++ flatten s 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(n2) worst case scenarios.
|The Wikibook Algorithm Implementation has a page on the topic of: Binary Tree Sort|