24.10.2019Diese Seite zeigt einen weiteren asymptotisch optimalen Sortieralgorithmus: Mergesort (engl. to merge - zusammenführen). Die Arbeitsweise von Mergesort ist erstaunlich einfach: beginne mit den Elementen in separaten Unterarrays und führe diese wiederholt zusammen unter beibehaltung der Sortierung. Dies führt zu immer längeren, sortierten Unterarrays, bis das ganze Array sortiert ist. Mergesort ist von der Geschwindigkeit her gleichauf mit Quicksort und Heapsort, zwei andere allgemeine Sortieralgorithmen. Der hauptsächliche Nachteil von Mergesort ist, dass es nicht in situ funktioniert, sondern ein zweites Array der selben Größe braucht.
Im obigen Panel werden zwei sortierte Arrays zu einem zusammengeführt, wobei die Sortierung beibehalten wird. Dies wird gemacht, indem das nächste Element für das Zielarray von den beiden möglichen Anfangselementen der Eingabearrays gewählt wird. Die Auswahl zwischen den beiden wird so getroffen wie es die Sortierung erfordert. In diesem Fall wird eine aufsteigende Reihenfolge sortiert, also wird immer das kleinere der beiden nächste Elemente ins Zielarray platziert. Das Zusammenführen funktioniert nur, weil die Eingabearrays bereits sortiert waren.
Um das ganze Array zu sortieren, platzieren wir am Anfang alle Elemente in ein separates Unterarray, und fangen dann an mit dem Zusammenführen, wie im vorherigen Panel gezeigt. Da die Ausgabe eines Merge-Schrittes das ursprüngliche Array nicht sofort überschreiben kann, wird die Ausgabe in ein zweites Array geleitet. Sobald die neue Sortierung im anderen Array ist, können neue Merge-Schritte die Daten wieder zurück in das ursprüngliche Array platzieren. Dies geht dann hin und her, bis einer der Arrays die vollständig sortierten Elemente enthält, wie man oben sehen kann.
Die grüne Füllung der Zahlenkästchen zeigt die Enden der sortierten Unterarrays an. Am Anfang sind alle Elemente in separaten Arrays, und alle Kästchen sind grün. Später zeigen einzelne grüne Kästchen die Grenzen zwischen den Unterarrays an. Die Sortierung ist fertig, wenn nur das letzte Kästchen grün ist. Man beachte, dass die Länge des ganzen Arrays keine Zweierpotenz ist, so das die Länge des letzten Unterarrays ein bisschen kürzer als die anderen ist. Dies ist aber kein Problem für Mergesort, da Arrays mit unterschiedlichen Längen zusammengeführt werden können.
Es gibt eine gute Möglichkeit diese Sortierprozedur zu beschleunigen: wenn wir mehrere Prozessorkerne zur verfügung haben, können diese die Unterarrays separat und parallel sortieren. Dies ist möglich weil die Grenzen der Unterarrays von Anfang an bekannt sind. Natürlich wird die Anzahl der parallelen Merge-Threads im Laufe der Sortierung verringert, so wie die Anzahl der Unterarrays geringer wird. Diese Prozedur wird oben gezeigt, man beachte wie viel schneller die frühen Schritte des Algorithmus ausgeführt werden.
Zum Abschluss dieser Seite möchte ich noch ein größeres Array mit Mergesort sortieren lassen. Dazu verwenden wir wieder die Sortierung mit nur einem Thread und ein Array mit 128 Zufallszahlen. Dies ist eine Zweierpotenz, und so kann man die Symmetrie der Sortierung einer solchen geraden Zahl von Elementen beobachten. Ich habe auch die Geschwindigkeit um den Faktor 2,5 erhöht.
Es gibt mehr zu Algorithmen und Datenstrukturen auf unserer Hauptseite zu entdecken.