Tim Sort
- Ω( n )
- Θ( n log n )
- O( n log n )
- space O( n )
Array
Comparator strip
Index down, time to the right
- Comparisons count only element-against-element checks; loop and index checks are never counted.
- Reads and writes include reads and writes to helper buffers (merge, counting, radix, bucket and tim sort).
- A swap counts once, as a swap. It is never also counted as a read or a write.
- Real time is the average time of the counted sort on this device over repeated runs, measured once before playback and independent of animation speed. Visual time is the time spent animating, excluding pauses.
How tim sort works
Tim sort is the hybrid used by Python and Java. It sorts short runs with insertion sort, which is fast on small and nearly sorted data, then merges the runs pairwise like merge sort.
Read more
This is a simplified version: fixed runs of 32 elements and bottom-up merging, without the run detection and galloping of the real thing. Merges are skipped when two neighbouring runs are already in order, so sorted input costs only about n comparisons.
| Best time | Ω( n ) | good |
|---|---|---|
| Average time | Θ( n log n ) | good |
| Worst time | O( n log n ) | good |
| Worst space | O( n ) | fair |
Big O notation gives the lower, average and upper bounds of an algorithm. Time complexity bounds the number of operations; space complexity bounds the extra memory it uses.