Tim Sort
HybridEin Hybrid aus Merge Sort und Insertion Sort, der natürliche Runs in realen Daten ausnutzt — der Algorithmus, der in Python und Java zum Einsatz kommt.
Live-Visualisierung
Komplexität
| Bester Fall | O(n) |
| Durchschnitt | O(n log n) |
| Schlechtester Fall | O(n log n) |
| Speicherkomplexität | O(n) |
| Stabiles Sortieren | Ja |
| In-Place | Nein |
Legende
O(1)- Konstant: Egal wie viele Elemente — der Aufwand bleibt gleich.
O(n)- Linear: Doppelt so viele Elemente → doppelt so viel Aufwand.
O(n log n)- Quasi-Linear: Wenig schlechter als linear — der Goldstandard für Sortieren.
O(n²)- Quadratisch: 10× mehr Elemente → 100× mehr Aufwand. Langsam bei großen Listen.
Stabil- Stabile Sortierung: Gleiche Werte behalten ihre ursprüngliche Reihenfolge zueinander.
In-Place- In-Place: Sortiert direkt im vorhandenen Speicher, ohne eine Kopie der Liste anzulegen.
Vergleichsbasiert- Vergleichsbasiert: Der Algorithmus entscheidet nur durch „ist A kleiner als B?" — funktioniert mit beliebigen Werten.
Nicht-Vergleichsbasiert- Nicht-Vergleichsbasiert: Nutzt die Struktur der Zahlen selbst (z. B. Ziffern) — kann dadurch schneller als O(n log n) sein.
Implementierung
TypeScript-Implementierung — direkt kopierbereit.
const MIN_MERGE = 32;
function timSort(arr: number[]): number[] {
const n = arr.length;
// Teilarrays der Größe MIN_MERGE per Insertion Sort sortieren
for (let i = 0; i < n; i += MIN_MERGE) {
insertionSortRange(arr, i, Math.min(i + MIN_MERGE - 1, n - 1));
}
// Sortierte Teilarrays schrittweise zusammenführen
for (let size = MIN_MERGE; size < n; size *= 2) {
for (let left = 0; left < n; left += 2 * size) {
const mid = Math.min(left + size - 1, n - 1);
const right = Math.min(left + 2 * size - 1, n - 1);
if (mid < right) mergeRanges(arr, left, mid, right);
}
}
return arr;
}
function insertionSortRange(arr: number[], left: number, right: number): void {
for (let i = left + 1; i <= right; i++) {
const key = arr[i];
let j = i - 1;
while (j >= left && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
arr[j + 1] = key;
}
}
function mergeRanges(arr: number[], l: number, m: number, r: number): void {
const left = arr.slice(l, m + 1);
const right = arr.slice(m + 1, r + 1);
let i = 0, j = 0, k = l;
while (i < left.length && j < right.length)
arr[k++] = left[i] <= right[j] ? left[i++] : right[j++];
while (i < left.length) arr[k++] = left[i++];
while (j < right.length) arr[k++] = right[j++];
}Wie es funktioniert
TimSort wurde 2002 von Tim Peters für Pythons list.sort() entwickelt und wird heute auch in Java (Arrays.sort für Objekte), Android und Swift verwendet. Es handelt sich um einen sorgfältig optimierten Hybridalgorithmus für reale Daten.
Funktionsweise: (1) Die Eingabe wird nach „Runs" durchsucht — natürlich aufsteigende oder absteigende Sequenzen. Absteigende Runs werden umgekehrt. Zu kurze Runs werden bis zu einer Mindestgröße (minrun, typischerweise 32–64) per Insertion Sort verlängert. (2) Ein Stack von Runs wird verwaltet; benachbarte Runs werden per Merge-Sort-Schritt zusammengeführt, wobei Invarianten den Stack ausbalanciert halten.
Warum er in der Praxis überlegen ist: Reale Daten sind selten zufällig — sie enthalten häufig teilweise sortierte Bereiche. TimSort nutzt diese Runs, um Vergleiche drastisch zu reduzieren, und erreicht bei bereits sortierten Eingaben O(n).
Hinweis: Die unten gezeigte Implementierung ist eine vereinfachte Lehrversion. Der vollständige Produktions-TimSort enthält weitere Optimierungen wie Galloping-Modus und präzise Minrun-Berechnung.