Funktionsweise von MergeSort |
Die grundsätzliche Idee |
Wir sehen uns zunächst in einem Beispiel an wie Mergesort sortiert. Dazu nehmen wir an, daß wir ein Array gegeben haben mit einer geraden Anzahl von Elementen. Zusätzlich sei die linke Hälfte des Arrays für sich sortiert, wie auch die rechte Hälfte. Das Array könnte also zum Beispiel so aussehen:
2 3 5 6 9 10 1 4 7 8 11 12Der Übersichtlichkeit halber haben wir die beiden Hälften in verschiedenen Farben dargestellt.
Zu diesem Zeitpunkt scheint dies extrem willkürlich zu sein. Der Leser möge diese Annahme einfach mal als gegeben hinnehmen.
Nun reservieren wir ein zweites Array mit derselben Größe. Es ist zu Beginn mit nullen gefüllt. Wir stellen es in Blau dar.
2 3 5 6 9 10 1 4 7 8 11 12 0 0 0 0 0 0 0 0 0 0 0 0Unser Ziel ist es jetzt, die Elemente vom Rot-Gelben Array ins Blaue Array so zu kopieren daß sie danach sortiert sind. Das ist aber einfach: man merkt sich einfach Zeiger auf das Rot-Gelbe Array und einen aufs blaue und kann dann schrittweise die Elemente kopieren:
2 3 5 6 9 10 1 4 7 8 11 12 ^ ^ 0 0 0 0 0 0 0 0 0 0 0 0 ^Und so weiter, bis wir am Schluß mit diesem Bild aufhören:2 3 5 6 9 10 1 4 7 8 11 12 ^ ^ 1 0 0 0 0 0 0 0 0 0 0 0 ^
2 3 5 6 9 10 1 4 7 8 11 12 ^ ^ 1 2 0 0 0 0 0 0 0 0 0 0 ^
2 3 5 6 9 10 1 4 7 8 11 12 ^ ^ 1 2 3 0 0 0 0 0 0 0 0 0 ^
2 3 5 6 9 10 1 4 7 8 11 12 ^ ^ 1 2 3 4 0 0 0 0 0 0 0 0 ^
2 3 5 6 9 10 1 4 7 8 11 12 ^ ^ 1 2 3 4 5 6 7 8 9 10 11 12 ^Natürlich ist damit der Algorithmus noch nicht fertig beschrieben: zunächst sind die sortierten Elemente jetzt in einem anderen Array. Um dieses Problem zu lösen kopieren wir sie im Moment einfach mal zurück.
Allerdings steht ja immer noch die Frage im Raum, wie man es denn fertig bringt daß das linke und das rechte Teilarray auch sortiert ist. Die Antwort darauf ist aber einfach: man sortiert sie einfach mit MergeSort.
Pseudocode |
Damit können wir jetzt bereits beschreiben wie der Algorithmus geht:
|
Natürlich ist dies nur sehr grob. Damit das jetzt auch tatsächlich funktioniert, muß man sich nur noch einige Details überlegen.
|
Effizienzsteigerung |
Damit haben wir MergeSort bereits beschrieben. Allerdings bemerken wir noch, daß wir noch relativ viel Zeit sparen können wenn wir nicht jedesmal ein neues Array b erzeugen. Das heißt, anstatt jedes mal ein temporäres Array zu machen, übergeben wir einfach dieses Array jedes mal wenn wir die Prozedur MergeSort aufrufen. Damit sparen wir etwas Zeit.
Stabilität |
Ein Vorteil von MergeSort gegenüber QuickSort ist, daß MergeSort stabil sortiert. Das heißt, daß die relative Ordnung zweier Elemente welche gleich sind beibehalten wird.
Damit braucht man nur beim Zusammenkopieren der beiden sortierten Teilarrays aufzupassen daß bei Gleichheit in der richtigen Reihenfolge kopiert wird.
Sortierung von Listen |
MergeSort kann recht einfach zum Sortieren von verketteten Listen eingesetzt werden. Wenn wir die rekursive Grundfunktion von oben betrachten:
|
dann erkennt man, dass zunächst in das Array 'hineinrekursiert' wird. Der Einfachheit halber nehmen wir mal an, dass dies glatt auf jeweils 2 Elemente geht.
Das Startarray (Aufruf 1)
5 1 7 8 6 3 9 2Rekursion (Aufruf 1.links)
5 1 7 8 6 3 9 2Rekursion (Aufruf 1.links.links)
5 1 7 8 6 3 9 2Sortierung
1 5 7 8 6 3 9 2Rekursion (Aufruf 1.links.rechts)
1 5 7 8 6 3 9 2Sortierung
1 5 7 8 6 3 9 2Merge von 1.links.links mit 1.links.rechts nach 1.links
1 5 7 8 6 3 9 2Rekursion (Aufruf 1.rechts)
1 5 7 8 6 3 9 2Rekursion (Aufruf 1.rechts.links)
1 5 7 8 6 3 9 2Sortierung
1 5 7 8 3 6 9 2Rekursion (Aufruf 1.rechts.rechts)
1 5 7 8 3 6 9 2Sortierung
1 5 7 8 3 6 2 9Merge von 1.rechts.links mit 1.rechts.rechts nach 1.rechts
1 5 7 8 2 3 6 9Merge von 1.links mit 1.rechts nach 1
1 2 3 5 6 7 8 9Die Verarbeitung läuft strikt von links nach rechts, was für Listen optimal ist.
Die Startliste
5 -> 1 -> 7 -> 8 -> 6 -> 3 -> 9 -> 2Der Algorithmus
Solange Elemente in der Startliste sind Hole die ersten beiden und sortiere sie in eine neue Liste Pushe die neue Liste auf einen Listenstack Solange die beiden letzten Listen auf dem Stack gleich groß sind Merge die beiden letzten Listen zusammen, pushe das Ergebnis Merge alle restlichen Listen in Stackfolge zusammenSchritt 1
1 -> 5Schritt 2
1 -> 5 7 -> 8Schritt 3
1 -> 5 -> 7 -> 8Schritt 4
1 -> 5 -> 7 -> 8 3 -> 6Schritt 5
1 -> 5 -> 7 -> 8 3 -> 6 2 -> 9Schritt 5
1 -> 5 -> 7 -> 8 2 -> 3 -> 6 -> 9Schritt 6
1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8 -> 9Da dieses Verfahren ein binäres Verhalten beim Merge aufweist, genügt die Verwendung eines unsigned Zählers, um zu bestimmen, wann gemerged werden soll.
Pass Binary Lists 1 0001 2 2 0010 2-2 => 4 3 0011 4-2 4 0100 4-2-2 => 4-4 => 8 5 0101 8-2 6 0110 8-2-2 => 8-4 7 0111 8-4-2 8 1000 8-4-2-2 => 8-4-4 => 8-8 => 16
|
Die verbliebene Liste auf dem Stack ist das sortierte Ergebnis.
Weitere Informationen |