Tree sort

<h2 id="efficiency">Efficiency</h2>
Adding one item to a binary search tree is on average an O(log n) process (in <a href="/facts/Big_O_notation/weFFjSWg">big O notation</a>). Adding n items is an O(n log n) process, making tree sorting a 'fast sort' process. Adding an item to an unbalanced binary tree requires O(n) time in the worst-case: When the tree resembles a <a href="/facts/Linked_list/Ik4JTgJW">linked list</a> (<a href="/facts/Binary_Tree/TDV7GMpu">degenerate tree</a>). This results in a worst case of 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 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 <a href="/facts/Self-balancing_binary_search_tree/W7WAsES0">self-balancing binary search tree</a>. Using such a tree, the algorithm has an O(n log n) worst-case performance, thus being degree-optimal for a <a href="/facts/Comparison_sort/X1PvE50c">comparison sort</a>. However, tree sort algorithms require separate memory to be allocated for the tree, as opposed to in-place algorithms such as <a href="/facts/Quicksort/1BeqhLAH">quicksort</a> or <a href="/facts/Heapsort/Cz22lLKq">heapsort</a>. On most common platforms, this means that <a href="/facts/Memory_management/vthLkUpz">heap memory</a> has to be used, which is a significant performance hit when compared to <a href="/facts/Quicksort/1BeqhLAH">quicksort</a> and <a href="/facts/Heapsort/Cz22lLKq">heapsort</a>. When using a <a href="/facts/Splay_tree/DHKCdoST">splay tree</a> as the binary search tree, the resulting algorithm (called <a href="/facts/Splaysort/Vpcbzecm">splaysort</a>) has the additional property that it is an <a href="/facts/Adaptive_sort/8BPWrNSD">adaptive sort</a>, meaning that its running time is faster than O(n log n) for inputs that are nearly sorted.

<h2 id="example">Example</h2>
The following tree sort algorithm in pseudocode accepts a <a href="/facts/Total_order/xnTtmuYJ">collection of comparable items</a> 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(Collection:items)
 BinaryTree:searchTree
 
 FOR EACH individualItem IN items
 Insert(searchTree, individualItem)
 
 InOrder(searchTree)

In a simple <a href="/facts/Functional_programming/cdxqPEIM">functional programming</a> form, the algorithm (in <a href="/facts/Haskell_(programming_language)/4Htv9WLu">Haskell</a>) 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.

<h2 id="external-links">External links</h2>

The Wikibook Algorithm Implementation has a page on the topic of: Binary Tree Sort

<ul><li><a href="https://web.archive.org/web/20161129234513/http://qmatica.com/DataStructures/Trees/BST.html">Binary Tree Java Applet and Explanation</a> at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a> (archived 29 November 2016)</li>
<li><a href="http://www.martinbroadhurst.com/articles/sorting-a-linked-list-by-turning-it-into-a-binary-tree.html">Tree Sort of a Linked List</a></li>
<li><a href="http://www.martinbroadhurst.com/cpp-sorting.html#tree-sort">Tree Sort in C++</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">McLuckie, Keith; Barber, Angus (1986). "Binary Tree Sort". Sorting routines for microcomputers. Basingstoke: Macmillan. ISBN 0-333-39587-5. OCLC 12751343. <a href="0-333-39587-5" target="_blank">0-333-39587-5</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
</ol>

Tree sort open-in-new

Tree sort