---
title: Tree sort
slug: tree-sort
qid: 
snapshot: enwiki-001333478496
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1333478496
tags: [109364843, 22904254, 22911879, 22994333, 23118434, 23603337, 24043274, 24623845, 24745122, 27152323]
---

# Tree sort

> [!note] Provenance
> Snapshot `enwiki-001333478496` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1333478496> · Licensed CC BY-SA 4.0

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. 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.

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. 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. 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 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 worst-case scenarios. == External links== == References==
