# Timsort visualised: insertion sort plus merge on runs

> Interactive Timsort: hybrid of insertion sort for small runs and stable bottom-up merge. Default sort in Python and Java, worst case O(n log n) and stable.

Address: https://marckimmel.de/en/informatik/sortieralgorithmen/tim-sort
Deutsche Fassung: https://marckimmel.de/informatik/sortieralgorithmen/tim-sort.md

Hybrid of Insertion Sort for small runs and Merge Sort for the merging phase.

Timsort is a hybrid algorithm combining the strengths of Insertion Sort and Merge Sort. It splits the array into small chunks called runs, sorts each run with Insertion Sort and then stably merges pairs of runs bottom-up. The full implementation also uses galloping heuristics, an adaptive minimum run length and a run stack with invariants; those are too complex for the visualizer, so we use a fixed run size of 4 and iterative merging. Best case (already sorted) detects existing runs and runs linearly O(n); average and worst case reach O(n log n). Memory is O(n) for the merge buffer, and the algorithm is stable.

Default sort in Python (sorted(), list.sort()), Java (Arrays.sort() for objects), Android, Swift and many other platforms. First choice in standard libraries because it is significantly faster than pure Merge Sort on real-world, partially sorted data.

## Related

- [Sorting Algorithms](https://marckimmel.de/en/informatik/sortieralgorithmen.md)