Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Mergesort Algorithmus [mit Animation, Deutsch]
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 60 Zeilen
- In diesem Video zeige ich euch, wie Mergesort funktioniert, wie man die Zeit- und Platzkomplexität von Mergesort bestimmt,
- und wie „Natural Mergesort“ den Algorithmus für teilweise vorsortierte Listen optimiert. Merge Sort funktioniert nach dem „Divide and Conquer“-Prinzip. Das heißt: Wir teilen die
- zu sortierende Liste von Elementen in immer kleinere Teil-Listen auf … und führen sie dann so wieder zusammen, dass jeweils eine sortierte Teilliste bzw. das sortierte Endergebnis entsteht.
- Wie das genau funktioniert, zeige ich euch an einem Beispiel. Wir wollen diese 8 Zahlen mit Mergesort sortieren.
- Wir teilen die Liste in der Mitte auf. Die zwei Teillisten teilen wir erneut jeweils in der Mitte auf.
- Und noch einmal. Jetzt haben wir nur noch Teillisten mit einem Element. Diese gelten als sortiert.
- Jetzt mergen wir jeweils zwei Teillisten zu einer. Wir beginnen mit der 3 und der 6.
- Wir nehmen jeweils das kleinste Element vom Anfang der zwei Teillisten, also zuerst die 3, dann die 6.
- Bei der 7 und der 1 nehmen wir zuerst die 1, dann die 7; hier ändert sich also die Reihenfolge der Elemente.
- Bei der 2 und der 5 bleibt sie wieder unverändert. Und bei der 8 und der 4 ändert sich die Reihenfolge wieder.
- Weiter geht es mit der 3–6 und der 1–7. Wir nehmen wieder jeweils das kleinste Element vom Anfang der zwei Teillisten, also zuerst die 1,
- da diese kleiner ist als die 3. Dann die 3, da diese kleiner ist als 7. Dann die 6, da auch diese kleiner ist als die 7. Und zuletzt die 7, da die andere Teilliste leer ist.
- Auf die gleiche Art mergen wir die 2–5 und die 4–8: Zuerst die 2, da diese kleiner ist als 4. Dann die 4, da diese kleiner ist als 5. Dann die 5,
- da diese kleiner ist als 8. Und schließlich die 8. Und zuletzt mergen wir diese zwei Teillisten zum Endergebnis.
- Das funktioniert nicht nur mit Zweierpotenzen, also mit zwei, vier, acht, 16 usw. Elementen. Aber damit lässt es sich besonders gut grafisch darstellen.
- Hier noch mal ein Beispiel mit elf Elementen. Eine ungerade Anzahl von Elementen teilen wir links oder rechts von der
- Mitte. Im Beispiel teile ich links von der Mitte. Noch einmal … und noch einmal.
- Jetzt haben wir acht Teillisten – fünf davon mit nur einem Element und drei mit zwei Elementen. Die mit zwei Elementen teilen wir noch einmal … und fügen sie als erstes wieder zusammen.
- Die anderen fünf Teillisten lassen wir dabei unverändert. Und so haben wir wieder acht Teillisten,
- die wir zu vier Teillisten mergen … dann zu 2 Teillisten … und schließlich zu einer Liste. Kommen wir zur Zeitkomplexität von Mergesort.
- Schauen wir uns zuerst die Teilungsphase an. Die Anzahl der zu sortierenden Elemente bezeichnen wir mit n.
- Bei n = 4 haben wir drei Teilungen. Bei n = 8 haben wir sieben Teilungen. Und bei n = 16 haben wir 15 Teilungen.
- Die Anzahl der Teilungen ist also n-1. Pro Teilung müssen wir die Mitte einer Liste bestimmen,
- der Aufwand dafür ist konstant. Konstanten sind für die O-Notation aber irrelevant, also auch die -1. Und wir erhalten als Zeitkomplexität für die Teilungsphase: O(n).
- Kommen wir zur Merge-Phase. Bei vier Elementen haben wir zwei Merge-Stufen,
- auf denen wir jeweils insgesamt vier Elemente mergen, nämlich vier mal eines und zwei mal zwei. Bei acht Elementen haben wir drei Merge-Stufen, auf denen wir jeweils acht Elemente mergen:
- acht mal eines, vier mal zwei und zwei mal vier. Und bei 16 Elementen haben wir vier Merge-Stufen, auf denen wir jeweils
- insgesamt 16 Elemente mergen: 16 mal eines, acht mal zwei, vier mal vier und zwei mal 8. Bei einer Verdopplung der Elemente erhöht sich die Anzahl der Merge-Stufen um eins. Die
- Anzahl der Merge-Stufen kann also berechnet werden als Logarithmus zur Basis 2 von n. Für die O-Notation können wir die Basis weglassen, und wir erhalten: O(log n).
- Da die jeweils zwei zu mergenden Listen in sich bereits sortiert sind, müssen beide genau einmal durchlaufen werden. Entsprechend ist der Aufwand
- proportional zur Anzahl der gemergten Elemente. Die Anzahl der Elemente pro Merge-Stufe ist n; entsprechend ist der Aufwand pro Merge-Stufe O(n).
- Den Gesamtaufwand für die Merge-Phase berechnen wir, indem wir den Aufwand pro Merge-Stufe mit der Anzahl der Merge-Stufe multiplizieren. Das können wir zusammenfassen zu: O(n × log n).
- Fügen wir nun Teilung- und Merge-Phasen zusammen, ergibt sich: O(n) + O(n × log n). Die kleinere Komplexitätsklasse O von n können wir weglassen;
- und als Gesamt-Zeitkomplexität bleibt: O(n × log n). Die Zeitkomplexität von Merge Sort lautet also: O(n × log n).
- Und das ist unabhängig davon, ob und wie die Zahlen vorsortiert sind. Wir haben also bei Mergesort keine Unterscheidung in Best, Worst und Average Case.
- Die Komplexitätsklasse O(n log n) bezeichnen wir als „quasilinear“, da der logarithmische Anteil bei großen n kaum noch ins Gewicht fällt und die
- Kurve fast nicht mehr von einer Linearen zu unterscheiden ist. Ein Beispiel:
- Auf meinem Laptop benötigt Mergesort für 100.000 zufällig angeordnete Zahlen etwa elf Millisekunden. Für eine Million Elemente 124 Millisekunden. Bei zehn
- Millionen Elementen 1,4 Sekunden. Und bei 100 Millionen Elementen 15 Sekunden. Das quasi-lineare Wachstum ist hier sehr gut zu erkennen.
- Bei Mergesort müssen wir nicht nur die Zeitkomplexität beachten, sondern auch die Platzkomplexität. Denn beim Mergen zweier Teillisten benötigen
- wir zusätzlichen Speicherplatz, um die gemergte Liste aufzunehmen. Hier noch mal ein Beispiel einer Merge-Phase mit acht Elementen.
- Für die ersten zwei Merges benötigen wir je eine zusätzliche Liste der Größe zwei. Um diese zwei Teillisten zu mergen, benötigen wir eine Liste der Größe vier.
- Die zwei Teillisten benötigen wir jetzt nicht mehr. Genauso mergen wir die hinteren vier Zahlen.
- Und zuletzt mergen wir diese zwei Teillisten. In diesem letzten Schritt benötigen wir den maximalen zusätzlichen Speicherplatz,
- nämlich doppelt so viel, wie wir Elemente haben, also 2 mal n. Es gibt noch einen alternativen Ansatz, der mit weniger Speicher auskommt.
- Wir mergen die ersten zwei Elemente und kopieren danach die gemergten und somit sortierten Elemente zurück in das Eingabe-Array.
- Wir mergen die nächsten zwei Elemente, kopieren auch diese zurück, mergen die ersten zwei Teillisten und kopieren auch diese zurück.
- Genauso gehen wir auf der rechten Seite vor. Und schließlich führen wir die letzten beiden Teillisten zusammen.
- Bei dieser Variante benötigen wir zusätzlichen Speicherplatz für maximal n Elemente, also halb so viele wie zuvor. Dafür haben wir allerdings zahlreiche zusätzliche Kopiervorgänge.
- So oder so – die Platzkomplexität von Mergesort ist O(n). Jetzt möchte ich euch noch eine Optimierung von Mergesort vorstellen, nämlich „Natural Mergesort“.
- Wenn wir uns noch einmal das erste Beispiel ansehen, können wir feststellen, dass unsere Zahlenfolge einige Teilfolgen enthält, die die Zahlen bereits in richtiger Reihenfolge enthalten.
- Diese Teilfolgen lassen sich durch einen einzigen Lauf über alle Zahlen ermitteln. Danach können wir direkt zur Merge-Phase übergehen.
- Wir mergen die ersten zwei Teillisten. Und wenn wir das Ergebnis mit der dritten Teillisten mergen,
- sind auch schon alle Zahlen fertig sortiert. Wenn die Zahlen komplett vorsortiert sind, wird das direkt beim ersten
- Durchlauf erkannt. Der Aufwand dafür wächst linear mit der Länge der Liste. Bei Natural Mergesort haben wir also auch einen Best Case,
- und dessen Zeitkomplexität ist: O(n). Die Zeitkomplexität im Average und Worst Case bleibt bei O(n × log n).
- Ich hoffe euch hat dieses Video über Mergesort gefallen. Auf meiner Webseite HappyCoders.eu findet ihr die Erklärung auch noch einmal zum Nachlesen. Einen
- Link dazu findet ihr in der Videobeschreibung. In dem Artikel findet ihr auch den Quellcode von Mergesort und eine Beschreibung von In-Place Mergesort, einer Variante, bei der die Merge-Phase
- ohne zusätzlichen Speicherplatz für die gemergten Teillisten auskommt. Wenn euch das Video gefallen hat, gebt mir gerne einen Daumen hoch, schreibt mir einen
- Kommentar, und ganz besonders freue ich mich natürlich, wenn ihr meinen Kanal abonniert. Bis bald und Happy Coding!
Zum Nachlesen
MergesortMergesort (von englisch merge ‚verschmelzen' und sort ‚sortieren') ist ein stabiler Sortieralgorithmus, der nach dem Prinzip teile und herrsche (divide and …
Merge-AlgorithmenMerge-Algorithmen werden in vielen Algorithmen als Unterprogramm verwendet. Ein bekanntes Beispiel dafür ist Mergesort.
Merge InsertionMerge Insertion (auch bekannt als Ford-Johnson-Algorithmus) ist in der Informatik ein rekursives, vergleichsorientiertes Sortierverfahren, das mit weniger …
QuicksortQuicksort (englisch quick ‚schnell' und to sort ‚sortieren') ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile …