StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
Americas
Europe
Schon die Römer verwendeten das sogenannte "Teile und herrsche"-Prinzip – allerdings wurde es bei ihnen noch "Divide et impera!" genannt. Dahinter verstecken sich verschiedene Theorien. Eine davon erklärt das Teile-und-Herrsche-Prinzip als eine ursprüngliche Kriegsstrategie, die verwendet wurde, um größere Feinde oder Königreiche zu zerspalten und mit einer Eroberung wieder zu vereinen. Nach genau diesem Prinzip funktioniert der Mergesort Sortieralgorithmus – nur natürlich…
Entdecke über 200 Millionen kostenlose Materialien in unserer App
Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken
Jetzt kostenlos anmeldenSchon die Römer verwendeten das sogenannte "Teile und herrsche"-Prinzip – allerdings wurde es bei ihnen noch "Divide et impera!" genannt. Dahinter verstecken sich verschiedene Theorien. Eine davon erklärt das Teile-und-Herrsche-Prinzip als eine ursprüngliche Kriegsstrategie, die verwendet wurde, um größere Feinde oder Königreiche zu zerspalten und mit einer Eroberung wieder zu vereinen.
Nach genau diesem Prinzip funktioniert der Mergesort Sortieralgorithmus – nur natürlich ohne die Streitereien und den Krieg! Was genau dahintersteckt und wie der Algorithmus funktioniert, erfährst Du jetzt.
Das Mergesort Sortierverfahren basiert auf dem sogenannten Divide and Conquer paradigm – also dem Teile-und-Herrsche-Prinzip. Was heißt das? Das Grundprinzip hinter dem Algorithmus ist es, eine Datenmenge immer wieder in zwei nahezu gleich große Teilmengen zu unterteilen. Das machst Du so lange, bis die Teilmengen nur noch jeweils ein Element enthalten. Dann wird das Ganze quasi in umgekehrter Richtung wieder zusammengeführt und dabei sortiert.
Falls Du Dir bei der Schreibweise des Sortierverfahren nicht ganz sicher sein solltest: Mergesort und Merge Sort sind beide korrekt.
Mergesort ist ein effizienter, stabiler Sortieralgorithmus, der eine Datenmenge in Teilmengen einteilt und diese dann rückwärts wieder zusammenführt. Der Algorithmus wurde erstmals 1945 von John von Neumann eingeführt.
Mergesort stammt aus dem Englischen von "merge", was so viel heißt wie verschmelzen und "sort", also sortieren.
Wie der Merge Sort Algorithmus funktioniert, lässt sich am besten an einem Beispiel erklären. Gegeben ist ein Array [5, 2, 8, 4, 9, 7, 1, 3, 6], das sortiert werden soll.
Teile das gegebene Array zunächst so lange, bis die einzelnen Arrays eine Länge von 1 haben. Da es sich bei diesem Beispiel um eine ungerade Anzahl an Elementen handelt, sind die Teilbereiche logischerweise nicht alle gleich groß. Das sorgt dafür, dass lediglich die Werte 3 und 6 in einem vierten Schritt erneut unterteilt werden müssen. Im nächsten Schritt beginnst Du dann bei diesen beiden Elementen.
Die Reihenfolge der Elemente verändert sich beim Aufteilen der Arrays noch nicht!
5 2 8 4 9 7 1 3 6 | ||||||||
5 2 8 4 | 9 7 1 3 6 | |||||||
5 2 | 8 4 | 9 7 | 1 3 6 | |||||
5 | 2 | 8 | 4 | 9 | 7 | 1 | 3 6 | |
3 | 6 |
Beginne nun damit, die einzelnen Arrays rückwärts wieder zusammenzuführen. In diesem Fall wird mit der 3 und der 6 begonnen.
3 | 6 | |||||||
5 | 2 | 8 | 4 | 9 | 7 | 1 | 3 6 |
In der nächsten Zeile beginnst Du dann wieder von links damit, jeweils die zwei nebeneinander liegenden Arrays zusammenzuführen. Vergleiche dabei die Elemente miteinander, haben sie nicht die richtige Reihenfolge, sortierst Du sie zusätzlich – in diesem Beispiel wird aufsteigend sortiert.
5 | 2 | 8 | 4 | 9 | 7 | 1 | 3 6 |
2 5 | 4 8 | 7 9 | 1 3 6 |
Führe nun wieder jeweils die benachbarten Arrays zu einem zusammen und sortiere dabei die Elemente, falls nötig.
2 5 | 4 8 | 7 9 | 1 3 6 |
2 4 5 8 | 1 3 6 7 9 |
Im letzten Schritt müssen jetzt nur noch die beiden verbliebenen Arrays zusammengeführt und sortiert werden.
2 4 5 8 | 1 3 6 7 9 |
1 2 3 4 5 6 7 8 9 |
Tada – fertig ist Dein mit Merge Sort sortiertes Array!
Noch einmal kurz und knapp: Wie gehst Du beim Merge Sort Algorithmus vor?
Wie sieht es mit der Komplexität beim Mergesort Verfahren aus? Unterschieden werden kann die Zeitkomplexität (Laufzeit) und die Platzkomplexität.
Mehr zur Komplexität und zur O-Notation findest Du in den Erklärungen zu den Sortierverfahren und zur O-Notation auf StudySmarter.
Die Laufzeit beträgt beim Mergesort in allen drei Anwendungsfällen (Best-Case, Average-Case, Worst-Case) O(n log n). Dabei macht es für die Laufzeit theoretisch keinen großen Unterschied, ob die Elemente bereits vorsortiert oder zufällig angeordnet sind.
Falls Du doch einen nicht unerheblichen Unterschied bei den Laufzeiten feststellen solltest, kann das an der Sprungvorhersage ("branch prediction") liegen. Einen kurzen Exkurs dazu findest Du in der Erklärung zum Bubble Sort auf StudySmarter.
Warum beträgt die Laufzeit beim Merge Sort O(n log n)?
Beim Unterteilen des Arrays wird bei einer Verdopplung der Eingabemenge nur ein Unterteilungsschritt mehr benötigt. Das heißt, die Anzahl von Teilungen beträgt log2 n.
Das Zusammenführen der unterteilten Arrays hat einen linearen Aufwand, also O(n). Das liegt daran, dass der Merge Sort Algorithmus keine verschachtelten Schleifen oder dergleichen enthält. Bei einer Verdopplung der Eingabegröße würde sich also auch der Aufwand verdoppeln.
Packt man nun beide Komplexitäten zusammen, erhält man n mal log2 n Schritte an Zerteilungen und Merge-Schritten. Die Laufzeit beträgt demnach: O(n log n).
Die Platzkomplexität beim Mergesort hat einen linearen Bedarf – sprich O(n). Das liegt daran, dass sich auch hier der zusätzlich benötige Speicherplatz verdoppelt, wenn die Eingabegröße verdoppelt wird. Der Algorithmus arbeitet in der Regel nicht in-place, da zusätzlicher Speicher benötigt wird.
Du kannst Merge Sort auch in-place, also ohne zusätzlichen Speicheraufwand implementieren. Allerdings verschlechtert sich dadurch die Laufzeit meist erheblich – Average-Case und Worst-Case liegen bei O(n2), anstatt bei O(n). Die Gesamtkomplexität würde O(n2 log n) statt O(n log n) betragen und der Algorithmus wäre nicht mehr wirklich effizient.
Im Folgenden werden noch ein paar weitere Begriffe rund um den Merge Sort Algorithmus geklärt. Dazu gehören:
Merge Sort ist ein stabiler Sortieralgorithmus. Der Punkt, an dem die ursprüngliche Reihenfolge verändert werden könnte, ist, wenn zwei Teilbereiche wieder zusammengeführt werden. Dabei wird geschaut, ob der größte Wert aus dem linken Teilbereich größer, kleiner oder gleich dem kleinsten Wert aus dem rechten Teilbereich ist. Wenn die Werte gleich sind, wird der linke zuerst kopiert – die Reihenfolge gleicher Elemente bleibt also immer erhalten.
Merge Sort arbeitet vergleichsbasiert, da beim Zusammenführen der einzelnen Elemente immer zwei miteinander verglichen und sortiert werden.
Der Merge Sort Algorithmus wird meist rekursiv implementiert. Du kannst den Algorithmus aber auch iterativ verwenden.
An dieser Stelle solltest Du noch wissen, dass die rekursive Implementation Datenmengen schneller durchläuft als die iterative Variante.
Ist Mergesort parallelisierbar? Die Antwort lautet: ja. Dafür gibt es zwei mögliche Ansätze: Entweder Du parallelisierst die Hauptmethode des Mergesort (merge()) oder Du parallelisierst die rekursiven Aufrufe des Mergesort.
Letztere Möglichkeit hat jedoch den Nachteil, dass die Leistungsfähigkeit von mehrkernigen CPUs nicht vollständig genutzt wird.
Alles, was Du bisher über Merge Sort gelernt haben solltest, findest Du in der nachfolgenden Übersicht:
Best-Case | Average-Case | Worst-Case | Platz-komplexität | Stabiles Verfahren | vergleichs-basiert | In-Place | Parallelisier-barkeit | iterativ/rekursiv |
O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Ja | Nein | Möglich | Beides |
Die Vor- und Nachteile des Mergesort findest Du in der folgenden Tabelle zusammengefasst:
Vorteile | Nachteile |
Effiziente Laufzeit mit O(n log n) | Es wird ein zusätzlicher Zwischenspeicher in der Größe der eigentlichen Datenmenge benötigt |
Kann Datenmengen sequenziell durcharbeiten, weswegen auch verkettete Listen sortiert werden können | Bei vorsortierten Datenmengen eher ineffizient |
Stabiler Sortieralgorithmus | Komplizierter zu implementieren als z. B. Insertion Sort |
Gut geeignet für sehr große, extern gespeicherte Datenmengen |
Für die Nachteile des Mergesort gibt es verschiedene Weiterentwicklungen. Eine ist der sogenannte "Natural Mergesort". Der Algorithmus soll verhindern, dass Datenmengen – unnötigerweise – unterteilt werden. Das Problem hast Du z. B. bei bereits relativ gut vorsortierten Datenmengen. Der Natural Mergesort Algorithmus identifiziert diese vorsortierten Bereiche und verhindert so unnötiges Teilen.
Bei absteigend und aufsteigend vorsortierten Datenmengen hätte Natural Mergesort dementsprechend jeweils eine Laufzeit von O(n).
Eine Weiterentwicklung des Natural Mergesort ist der Timsort Algorithmus. Dabei werden Teile der Datenmenge mit Insertion Sort sortiert.
Eine häufig gestellte Frage ist, welcher Sortieralgorithmus ist schneller: Mergesort oder Quicksort? Das lässt sich relativ schnell beantworten: Quicksort ist der schnellere Algorithmus. Das liegt, kurz gesagt, daran, dass der Quicksort nur die Elemente verschiebt, die sich an der falschen Position befinden. Beim Merge Sort werden hingegen jedes Mal alle Elemente kopiert.
Du willst noch mehr zum Quicksort erfahren? Dann schau doch auf der gleichnamigen Erklärung bei StudySmarter vorbei.
Mehr Vor- und Nachteile von Mergesort und Quicksort findest Du in der nachfolgenden Tabelle:
Mergesort | Quicksort | |
Vorteile | Zeitkomplexität ist im Worst-Case nie schlechter als O(n log n) | Für unsortierte Datenmengen etwa doppelt so schnell, für vorsortierte Datenmengen 4-mal so schnell |
Stabiler Sortieralgorithmus | ||
Nachteile | Langsamere Laufzeit als Quicksort | Zeitkomplexität ist im Worst-Case O(n2) |
Zusätzlicher Speicher mit O(n) notwendig | Instabiler Sortieralgorithmus |
Trotz des besseren Worst-Cases wird in der Praxis eher Quicksort als Mergesort verwendet!
Für ein besseres Verständnis folgen nun noch ein paar weitere (Code-)Beispiele zum Mergesort.
Die Anwendung von Mergesort erfolgt z. B. in folgenden Fällen:
Eine Möglichkeit zur Implementation von Mergesort wird Dir mit dem folgenden Pseudocode vorgestellt:
mergesort (Array array) // Das Array wird beim Unterteilen in jeweils zwei gleich große Hälften (links und rechts) unterteilt // Ist das Array <= 1 wird dieser Schritt beendet if array <= 1 do int mitte = array.length / 2 int links -> i <= mitte - 1 int rechts -> i >= array.length - mitte - 1 links = mergesort(links) rechts = mergesort(rechts) return zusammenfuehren(links, rechts) // Funktion zum Zusammenführen der Teilbereiche zu einem neuen Array zusammenfuehren(links, rechts) int n int indexlinks = length(links) – 1 int indexrechts = length(rechts) – 1 int indexergebnis = 0 // Funktion wird durchgeführt, solange der linke und rechte Teilbereich nicht leer sind while indexlinks < links.length und indexrechts < rechts.length // Ist das erste Element des linken Arrays kleiner gleich dem ersten Element der rechten Seite if links[indexlinks] < rechts[indexrechts] // dann füge das erste Element von links in das neue Array ein und entferne es aus dem alten neuesArray[indexergebnis] = links[indexlinks] indexlinks += 1 // ansonsten füge das erste Element von rechts ins neue Array ein und entferne es aus dem alten else neuesArray[indexergebnis] = rechts[indexrechts] indexrechts += 1 indexergebnis += 1 // Solange das linke Array nicht leer ist while indexlinks < links.length // füge das erste Element aus dem linken Bereich in das neue Array ein und entferne es aus dem alten neuesArray[indexergebnis] = links[indexlinks] indexlinks += 1 indexergebnis += 1 // Solange das rechte Array nicht leer ist while (indexrechts < rechts.length) // füge das erste Element aus dem rechten Bereich in das neue Array ein und entferne es aus dem alten neuesArray[indexergebnis] = rechts[indexrechts] indexrechts += 1 indexergebnis += 1 // Gib das neue Array zurück return neuesArray
Mergesort vs. Quicksort:
Mergsort ist stabil und hat immer eine Zeitkomplexität von O(n log n)
Quicksort ist instabil und die Zeitkomplexität beträgt im Worst-Case "nur" O(n2)
Trotzdem ist Quicksort schneller beim Sortieren als Mergesort
Mergesort Anwendung: Mergesort wird häufig bei verketteten Listen angewendet oder wenn ein externer Speicher verwendet wird.
Mergesort teilt eine Datenmenge immer wieder in zwei gleich große Teilmengen ein und fügt diese im Anschluss schrittweise wieder zusammen und sortiert die Elemente dabei.
Mergesort ist ein stabiler Algorithmus, weil beim Zusammenführen gleich große Werte in ihrer Reihenfolge nicht vertauscht werden.
Mergesort hat im Best-, Average- und Worst-Case eine Laufzeit von O(n log n) und gehört somit zu den effizienten Algorithmen.
Quicksort verschiebt Elemente im Grunde einfach nur. Mergesort kopiert Elemente und hat deswegen den deutlich größeren zusätzlichen Speicher. Deswegen ist Quicksort in der Regel schneller als Mergesort.
Wie möchtest du den Inhalt lernen?
94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmelden94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmeldenWie möchtest du den Inhalt lernen?
Kostenloser informatik Spickzettel
Alles was du zu . wissen musst. Perfekt zusammengefasst, sodass du es dir leicht merken kannst!
Sei rechtzeitig vorbereitet für deine Prüfungen.
Teste dein Wissen mit spielerischen Quizzes.
Erstelle und finde Karteikarten in Rekordzeit.
Erstelle die schönsten Notizen schneller als je zuvor.
Hab all deine Lermaterialien an einem Ort.
Lade unzählige Dokumente hoch und habe sie immer dabei.
Kenne deine Schwächen und Stärken.
Ziele Setze dir individuelle Ziele und sammle Punkte.
Nie wieder prokrastinieren mit unseren Lernerinnerungen.
Sammle Punkte und erreiche neue Levels beim Lernen.
Lass dir Karteikarten automatisch erstellen.
Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.
Melde dich an für Notizen & Bearbeitung. 100% for free.