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 when sorting the elements of a stream from a file. Several other sorts would have to load the elements to a temporary data structure, whereas in a tree sort the act of loading the input into a data structure is sorting it.
Adding one item to a binary search tree is on average an O(log(n)) process, so adding n items is an O(n log(n)) process, making Tree Sort a so-called, 'fast sort'. But adding an item to an unbalanced binary tree needs O
) time in the worst-case, when the tree resembles a linked list
), causing a worst case of O(n<sup>2</sup>) for this sorting algorithm.The worst case scenario then is triggered by handing a Tree Sort algorithm an already sorted set. This would make the time needed to insert all elements into the binary tree O(n<sup>2</sup>). The dominant process in the Tree Sort algorithm is the "insertion" into the binary tree, assuming that the time needed for retrieval is O(n).
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.
In a simple functional programming
form, the algorithm (in Haskell
) would look something like this:<source... Read More