Interactive demo
Timsort Visualization
Timsort, written by Tim Peters for Python in 2002, is a merge sort that looks for runs: parts of the array that are already in order. Real data often contains such runs, and timsort uses them instead of sorting from scratch.
Choose “Sorted”, “Reversed” or “Nearly sorted”: timsort needs only a few steps. The dashed lines separate the runs on the stack.
Playback
- Comparisons
- 0
- Writes
- 0
Array
Legend
- Not in a run yet
- In a run
- Inserted or copied element
- Compared heads
- Final position
Runtime and properties
Best case
O(n)
Sorted or reversed input is a single run: n − 1 comparisons and done.
Average case
O(n log n)
Short runs are extended to a minimum length, then merged in a balanced way.
Worst case
O(n log n)
The rules for merging keep the run lengths balanced, like merge sort.
Extra memory
O(n)
Merging copies the shorter of two runs, at most n / 2 elements.
Stable
Yes
Runs are only reversed if they are strictly descending, and ties keep the left element first.
In-place
No
The shorter run is copied to a temporary 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 | 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 this page | 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. Find runs
Timsort walks through the array and finds the next run. A strictly descending run is simply reversed. A run shorter than the minimum run length is extended with binary insertion sort.
2. Keep the stack balanced
Every run goes onto a stack. Whenever the run lengths on the stack become unbalanced, neighboring runs are merged, so the merges stay about as balanced as in merge sort.
3. Simplified here
This visualization uses a minimum run length of 4 (the original uses 32 to 64 and sorts arrays below 64 elements with binary insertion sort alone) and merges element by element. The original also switches to “galloping” when one run keeps winning, and current Python merges runs with the newer powersort strategy.
Credits
- Timsort was created by Tim Peters. His description of the algorithm is listsort.txt in the CPython source code; this visualization follows its original merge rules in a simplified form.