Fortschritt:7% (1/15)
Karte 1 von 15Frage:
Was ist Mergesort?
Lernkarten - Sortieralgorithmen: Mergesort
Mergesort Algorithmus: Stabile Sortierung einfach erklärt
Lerne den Mergesort Algorithmus verstehen: Entdecke, wie stabile Sortierung funktioniert und warum dieser Divide-and-Conquer-Ansatz so effizient ist.
📘 Lernmodus⏱️ 10–15 Minuten🎓 Prüfungsrelevant
Häufige Fragen zur Sortieralgorithmen: Mergesort
Was ist Mergesort und wie funktioniert es grundsätzlich?
Mergesort ist ein effizienter Sortieralgorithmus, der nach dem Divide-and-Conquer-Prinzip arbeitet. Er teilt die zu sortierende Liste rekursiv in kleinere Teillisten auf, sortiert diese und fügt sie anschließend in der richtigen Reihenfolge wieder zusammen.
Warum wird Mergesort als 'stabil' bezeichnet?
Ein Sortieralgorithmus ist stabil, wenn Elemente mit gleichem Wert ihre ursprüngliche relative Reihenfolge beibehalten. Mergesort erfüllt diese Eigenschaft, da beim Zusammenfügen der Teillisten gleiche Elemente aus der linken Liste vor denen aus der rechten Liste eingefügt werden.
Wie hoch ist die Zeitkomplexität von Mergesort?
Mergesort hat eine Zeitkomplexität von O(n log n) sowohl im besten als auch im schlechtesten Fall. Diese konstante Laufzeit macht ihn besonders zuverlässig für große Datenmengen.
Was sind die Hauptvorteile von Mergesort gegenüber anderen Sortieralgorithmen?
Mergesort bietet eine garantiert gute Laufzeit von O(n log n), ist stabil und funktioniert gut bei großen Datenmengen. Außerdem lässt er sich gut parallelisieren und eignet sich hervorragend für das Sortieren von verketteten Listen.
Welche Nachteile hat Mergesort?
Der Hauptnachteil von Mergesort ist sein zusätzlicher Speicherbedarf von O(n), da temporäre Arrays für das Zusammenfügen benötigt werden. Für kleine Datenmengen kann er auch langsamer sein als einfachere Algorithmen wie Insertionsort.