Tree sort

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Tree sort" – news · newspapers · books · scholar · JSTOR (June 2022) (Learn how and when to remove this message)

Tree sort

Class	Sorting algorithm
Data structure	Array
Worst-case performance	O(n²) (unbalanced) O(n log n) (balanced)
Best-case performance	O(n log n) [citation needed]
Average performance	O(n log n)
Worst-case space complexity	Θ(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.^[1] 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.