Timsort
Hybrid aus Insertion Sort für kleine Runs und Merge Sort für das Zusammenfassen.
- Vergleiche 0
- Tauschvorgänge 0
- sortierte Indizes 0
- Vergleich
- Tausch
- sortiert
Pseudocode
1 runSize = 4
2 for start = 0 to n - 1 step runSize
3 end = min(start + runSize - 1, n - 1)
4 insertionSort(start, end)
5 for size = runSize while size < n; size *= 2
6 for left = 0 to n - 1 step 2*size
7 mid = min(left + size - 1, n - 1)
8 right = min(left + 2*size - 1, n - 1)
9 if mid < right: merge(left, mid, right)
10
11 insertionSort(lo, hi):
12 for i from lo + 1 to hi
13 key = a[i]; j = i - 1
14 while j >= lo and a[j] > key
15 a[j + 1] = a[j]; j = j - 1
16 a[j + 1] = key
17
18 merge(lo, mid, hi):
19 L = a[lo..mid]; R = a[mid+1..hi]
20 i = 0; j = 0; k = lo
21 while i < |L| and j < |R|
22 if L[i] <= R[j]: a[k++] = L[i++]
23 else: a[k++] = R[j++]
24 copy remaining L into a
25 copy remaining R into a
Schritt-Log
Funktionsweise, Laufzeit und Speicher
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.
Komplexität
- Best Case
O(n) - Average Case
O(n log n) - Worst Case
O(n log n) - Zusatz-Speicher
O(n)
Wann verwenden?
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.