Interactive demo
Tree Sort Visualization
Tree sort inserts every element into a binary search tree and then reads the tree in order. On random input the tree stays flat and the sort is fast, on sorted input it degenerates into a long chain.
Choose “Sorted” or “Reversed”: the tree becomes a single long branch, the worst case.
Playback
- Comparisons
- 0
- Writes
- 0
Array
Legend
- Element in the array
- Element being inserted
- Compared node
- Node in the tree
- Final position
Runtime and properties
Best case
O(n log n)
A balanced tree: every insertion only goes about log n levels deep.
Average case
O(n log n)
In a tree built from random input, a node is on average about 1.4 · log n levels deep.
Worst case
O(n²)
Sorted or reversed input degenerates the tree into a list of n levels.
Extra memory
O(n)
Every element gets its own tree node.
Stable
Yes
Equal elements go to the right, so reading in order keeps their order.
In-place
No
The tree is built outside the array.
n is the number of elements. O(n log n) is the best a sorting algorithm based on comparisons can achieve.
Compared with the other sorting algorithms
| Algorithm | Best case | Average case | Worst case | Extra memory | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Shell sort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | No | Yes |
| Tree sort this page | O(n log n) | O(n log n) | O(n²) | O(n) | Yes | No |
| Tournament sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Patience sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Block sort | O(n) | O(n log n) | O(n log n) | O(1) | Yes | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
1. Binary search tree
Every node has at most two children: everything smaller is in its left subtree, everything larger or equal in its right one.
2. Insert
A new element starts at the root and walks down, left if it is smaller, right otherwise, until it finds a free place. Equal elements go right, which keeps the sort stable.
3. Read in order
Reading the tree in order (left subtree, node, right subtree) returns all elements sorted. How fast tree sort is depends on the depth of the tree.