Algorithmen und Datenstrukturen · Senior · Frage 31 von 75
Warum schneidet Timsort auf realen Daten so gut ab?
- 1Es wechselt bei Zahlen ganz zu Counting Sort
- 2Es findet sortierte Abschnitte und mischt sie
- 3Es sortiert parallel auf allen CPU-Kernen
Antwort zeigen
Richtige Antwort: Es findet sortierte Abschnitte und mischt sie
Erklärung
Reale Daten sind oft teilweise geordnet: angehängte Logs, meist sortierte Listen. Timsort findet aufsteigende (oder umgedrehte absteigende) Abschnitte, verlängert kurze mit Insertion Sort und führt sie mit Galloping zusammen, was bei fast sortierter Eingabe O(n) nahekommt.