Tree sort is a sorting algorithm that builds a binary search tree from the elements to be sorted and then traverses that tree in order, so the elements come out in sorted order. Its typical use is sorting elements online: after each insertion, the set of elements seen so far is already available in sorted order. It can also serve as a one-time sort, but it is equivalent to quicksort in that both recursively partition the elements around a pivot, and because quicksort works in place with lower overhead, tree sort has few advantages over it. Using a self-balancing tree gives it a better worst case, at the price of even more overhead.
Facts
Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Connections
In Field
Source Tree sort (Wikipedia)
Sources
1. Tree sort (Wikipedia)
Lead section
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.
Article text
Using such a tree, the algorithm has an O(n log n) worst-case performance
In Field: Algorithms and Complexity Theory, Lead
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.
In Group: Comparison Sorting Algorithms, Lead
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.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.