{{Short description|Type of sorting algorithm}} {{more citations needed|date=June 2022}} {{Infobox Algorithm |class=Sorting algorithm |image=200px |data=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 (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: 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 (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 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 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) 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}} * {{webarchive|url=https://web.archive.org/web/20220121202457/https://www.martinbroadhurst.com/cpp-sorting.html |date=21 January 2022|title=Tree Sort in C++}}
== References== {{reflist}} {{sorting}}
Category:Sorting algorithms Category:Online sorts