View source for Tree sort

{{Short description|Type of sorting algorithm}}
{{more citations needed|date=June 2022}}
{{Infobox Algorithm
|class=[[Sorting algorithm]]
|image=[[File:Binary tree sort(2).png|200px]]
|data=[[Array data structure|Array]]
|time={{math|''O''(''n''²)}} (unbalanced)
{{math|''O''(''n'' log ''n'')}} (balanced)
|best-time={{math|''O''(''n'' log ''n'')}} {{Citation needed|date=September 2014}}
|average-time={{math|''O''(''n'' log ''n''}})
|space={{math|Θ(''n'')}}
|optimal=Yes, if balanced
}}

A '''tree sort''' is a [[sort algorithm]] that builds a [[binary search tree]] from the elements to be sorted, and then traverses the tree ([[Tree traversal|in-order]]) so that the elements come out in sorted order.<ref name="McLuckie Barber p. ">{{cite book | chapter = Binary Tree Sort | last=McLuckie | first=Keith | last2=Barber | first2=Angus | title=Sorting routines for microcomputers | publisher=Macmillan | publication-place=Basingstoke | date=1986 | isbn=0-333-39587-5 | oclc=12751343 | page=}}</ref> Its typical use is sorting elements [[online algorithm|online]]: after each insertion, the set of elements seen so far is available in sorted order.

Tree sort can be used as a one-time sort, but it is equivalent to [[quicksort]] as both recursively partition the elements based on a pivot, and since quicksort is in-place and has lower overhead, tree sort has few advantages over quicksort. It has better worst case complexity when a self-balancing tree is used, but even more overhead.

== Efficiency ==
Adding one item to a binary search tree is on average an {{math|''O''(log ''n'')}} process (in [[big O notation]]). Adding n items is an {{math|''O''(''n'' log ''n'')}} process, making tree sorting a 'fast sort' process. Adding an item to an unbalanced binary tree requires {{math|''O''(''n'')}} time in the worst-case: When the tree resembles a [[linked list]] ([[Binary Tree#Types of binary trees|degenerate tree]]). This results in a worst case of {{math|''O''(''n''²)}} 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 {{math|''O''(''n'' log ''n'')}} 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 {{math|''O''(''n'' log ''n'')}} 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 [[Memory management#HEAP|heap memory]] has to be used, which is a significant performance hit when compared to [[quicksort]] and [[heapsort]]{{citation needed|date=December 2019}}. 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 {{math|''O''(''n'' log ''n'')}} for inputs that are nearly sorted.

== Example ==
The following tree sort algorithm in pseudocode accepts a [[total order|collection of comparable items]] and outputs the items in ascending order:

{{syntaxhighlight|lang=sql|

 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(Collection:items)
     BinaryTree:searchTree
    
     FOR EACH individualItem IN items
         Insert(searchTree, individualItem)
    
     InOrder(searchTree)
}}

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

<syntaxhighlight lang="haskell">
 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
</syntaxhighlight>

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

== External links==
{{wikibooks|Algorithm Implementation|Sorting/Binary Tree Sort|Binary Tree Sort}}

* {{webarchive|url=https://web.archive.org/web/20161129234513/http://qmatica.com/DataStructures/Trees/BST.html |date=29 November 2016|title=Binary Tree Java Applet and Explanation}}
* {{webarchive|url=https://web.archive.org/web/20160810130303/https://www.martinbroadhurst.com/articles/sorting-a-linked-list-by-turning-it-into-a-binary-tree.html |date=10 August 2016|title=Tree Sort of a Linked List}}
* [http://www.martinbroadhurst.com/cpp-sorting.html#tree-sort Tree Sort in C++]

== References==
{{reflist}}
{{sorting}}

[[Category:Sorting algorithms]]
[[Category:Online sorts]]