# Tree sort

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Tree_sort
> Markdown URL: https://mediated.wiki/source/Tree_sort.md
> Source: https://en.wikipedia.org/wiki/Tree_sort
> Source revision: 1333478496
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Type of sorting algorithm}}
{{more citations needed|date=June 2022}}
{{Infobox Algorithm
|class=[Sorting algorithm](/source/Sorting_algorithm)
|image=200px
|data=[Array](/source/Array_data_structure)
|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](/source/sort_algorithm) that builds a [binary search tree](/source/binary_search_tree) from the elements to be sorted, and then traverses the tree ([in-order](/source/Tree_traversal)) 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](/source/online_algorithm): 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](/source/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](/source/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](/source/linked_list) ([degenerate tree](/source/Binary_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](/source/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](/source/comparison_sort). However, tree sort algorithms require separate memory to be allocated for the tree, as opposed to in-place algorithms such as [quicksort](/source/quicksort) or [heapsort](/source/heapsort). On most common platforms, this means that [heap memory](/source/Memory_management) has to be used, which is a significant performance hit when compared to [quicksort](/source/quicksort) and [heapsort](/source/heapsort){{citation needed|date=December 2019}}. When using a [splay tree](/source/splay_tree) as the binary search tree, the resulting algorithm (called [splaysort](/source/splaysort)) has the additional property that it is an [adaptive sort](/source/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](/source/total_order) 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](/source/functional_programming) form, the algorithm (in [Haskell](/source/Haskell_(programming_language))) 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

---
Adapted from the Wikipedia article [Tree sort](https://en.wikipedia.org/wiki/Tree_sort) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Tree_sort?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.