Question 1

Was ist Mergesort und wie funktioniert es grundsätzlich?

Accepted Answer

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.

Question 2

Warum wird Mergesort als 'stabil' bezeichnet?

Accepted Answer

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.

Question 3

Wie hoch ist die Zeitkomplexität von Mergesort?

Accepted Answer

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.

Question 4

Was sind die Hauptvorteile von Mergesort gegenüber anderen Sortieralgorithmen?

Accepted Answer

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.

Question 5

Welche Nachteile hat Mergesort?

Accepted Answer

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.

Mergesort – Stabiler und effizienter Sortieralgorithmus erklärt

Lernkarten zu Sortieralgorithmen: Mergesort