# Tree sort

Class Sorting algorithm Array O(n²) (unbalanced) O(n log n) (balanced) O(n log n)[citation needed] O(n log n) Θ(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 sorting elements adaptively: 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 O(log n) process (in big O notation), so adding n items is an O(n log n) process, making tree sort a '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. This worst case occurs when the algorithm operates on an already sorted set, or one that is nearly sorted. Expected O(log n) time can however be achieved in this case by shuffling the array.

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 for a comparison sort. When using a splay tree as the binary search tree, the resulting algorithm (called splaysort) has the additional property that it is an adaptive sort, meaning that its running time is faster than O(n log n) for inputs that are nearly sorted.

## Example

The following tree sort algorithm in pseudocode accepts an array of comparable items and outputs the items in ascending order:

```STRUCTURE BinaryTree
BinaryTree:LeftSubTree
Object:Node
BinaryTree:RightSubTree

PROCEDURE Insert(BinaryTree:searchTree, Object:item)
IF searchTree.Node 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)

PROCEDURE InOrder(BinaryTree:searchTree)
IF searchTree.Node IS NULL THEN
EXIT PROCEDURE
ELSE
InOrder(searchTree.LeftSubTree)
EMIT searchTree.Node
InOrder(searchTree.RightSubTree)

PROCEDURE TreeSort(Array:items)
BinaryTree:searchTree

FOR EACH individualItem IN items
Insert(searchTree, individualItem)

InOrder(searchTree)
```

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 s)
| x <= y = Node (insert x 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
```

In the above implementation, both the insertion algorithm and the retrieval algorithm have O(n²) worst-case scenarios.