# Timsort visualisieren: Insertion Sort plus Merge auf Runs

> Timsort interaktiv: Insertion Sort für kleine Runs und stabiler Bottom-up-Merge. Standard in Python und Java, O(n log n) im Worst Case und stabil.

Adresse: https://marckimmel.de/informatik/sortieralgorithmen/tim-sort
English version: https://marckimmel.de/en/informatik/sortieralgorithmen/tim-sort.md

Hybrid aus Insertion Sort für kleine Runs und Merge Sort für das Zusammenfassen.

Timsort ist ein Hybrid-Algorithmus, der die Stärken von Insertion Sort und Merge Sort kombiniert. Er teilt das Array in kleine Stücke (sogenannte Runs), sortiert jeden Run mit Insertion Sort und mergt anschließend die Runs in einem stabilen, bottom-up Merge-Verfahren paarweise zusammen. Die echte Implementierung nutzt zusätzlich Galloping-Heuristiken, eine adaptive Berechnung der minimalen Run-Größe und einen Run-Stack mit Invarianten, die für den Visualizer zu komplex wären; daher rechnen wir hier mit fester Run-Größe 4 und iterativem Merge. Im besten Fall (bereits sortierte Eingabe) erkennt Timsort die existierenden Runs und läuft linear (O(n)), im Average und Worst Case erreicht er O(n log n). Der Speicherbedarf liegt bei O(n) wegen des Merge-Puffers, und der Algorithmus ist stabil.

Standard-Sortier-Algorithmus in Python (sorted(), list.sort()), Java (Arrays.sort() für Objekte), Android, Swift und vielen weiteren Plattformen. Erste Wahl in Sprachen-Standardbibliotheken, weil er auf realen, oft teilweise sortierten Daten erheblich schneller ist als reines Merge Sort.

## Weiter

- [Sortieralgorithmen](https://marckimmel.de/informatik/sortieralgorithmen.md)