DseWiki: MergeSort

MergeSort ist ein Sortier-Algorithmus welcher asymptotisch optimale Laufzeit hat. In praktischen Implementierungen ist er zwar nicht ganz so schnell wie QuickSort, hat dafür den Vorteil daß er stabil sortiert (siehe StabilesSortieren).

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 12

Der Ü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 0

Unser 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
  ^

  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
              ^

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  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:

procedure Mergesort(Array a) Sortiere die linke Hälfte von A mit Mergesort Sortiere die rechte Hälfte von A mit Mergesort Kopiere beide Hälften zusammen in ein neues Array mit der obigen Methode endprocedure

Natürlich ist dies nur sehr grob. Damit das jetzt auch tatsächlich funktioniert, muß man sich nur noch einige Details überlegen.

procedure Mergesort(int[] a, int L, int R) // Sortiert das Array a von der Stelle L bis zur Stelle (aber ohne) R if L + 1 >= R then return end if // Nur eine Zahl kann man leicht sortieren m := (L+R) / 2 // Wichtig ist hier daß M aus dem [L,R) ist, //] // denn dann bricht das sicher einmal ab. Mergesort(a, L, M) Mergesort(a, M, R) int[] b = new int[R-L] // Neues Array der grösse R-L int copyL, copyR, copyTo // Die 3 Zeiger copyL = L copyR = M copyTo = 0 while copyTo < R-L do if a[copyL] <= a[copyR] then b[copyTo] = a[copyL] copyL = copyL + 1 else b[copyTo] = a[copyR] copyR = copyR + 1 end if copyTo = copyTo + 1 end while // Und nun noch zurückkopieren: copyTo = 0 while (L < R) do a[L] = b[copyTo] L = L+1 copyTo = copyTo + 1 end while endprocedure

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   2

Rekursion (Aufruf 1.links)

  5   1   7   8   6   3   9   2

Rekursion (Aufruf 1.links.links)

  5   1   7   8   6   3   9   2

Sortierung

  1   5   7   8   6   3   9   2

Rekursion (Aufruf 1.links.rechts)

  1   5   7   8   6   3   9   2

Sortierung

  1   5   7   8   6   3   9   2

Merge von 1.links.links mit 1.links.rechts nach 1.links

  1   5   7   8   6   3   9   2

Rekursion (Aufruf 1.rechts)

  1   5   7   8   6   3   9   2

Rekursion (Aufruf 1.rechts.links)

  1   5   7   8   6   3   9   2

Sortierung

  1   5   7   8   3   6   9   2

Rekursion (Aufruf 1.rechts.rechts)

  1   5   7   8   3   6   9   2

Sortierung

  1   5   7   8   3   6   2   9

Merge von 1.rechts.links mit 1.rechts.rechts nach 1.rechts

  1   5   7   8   2   3   6   9

Merge von 1.links mit 1.rechts nach 1

1 2 3 5 6 7 8 9

Die Verarbeitung läuft strikt von links nach rechts, was für Listen optimal ist.

Die Startliste

  5 -> 1 -> 7 -> 8 -> 6 -> 3 -> 9 -> 2

Der 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 zusammen

Schritt 1

  1 -> 5

Schritt 2

  1 -> 5     7 -> 8

Schritt 3

  1 -> 5 -> 7 -> 8

Schritt 4

  1 -> 5 -> 7 -> 8     3 -> 6

Schritt 5

  1 -> 5 -> 7 -> 8     3 -> 6     2 -> 9

Schritt 5

  1 -> 5 -> 7 -> 8     2 -> 3 -> 6 -> 9

Schritt 6

  1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8 -> 9

Da 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

 
 unsigned Pass, p, Lists;

 Next2(Stack, Srclist); 
     /* Holt die nächsten beiden Elemente (oder das letzte einzelne) aus der Srclist, 
        sortiert sie in eine neue Liste und pusht die Liste auf den Stack. */

 Merge(Stack);
     /* Merged die beiden obersten Listen auf dem Stack. */

 Pass = 0;
 Lists = 0;
 while (Srclist)
 {
     Next2(Stack, Srclist); Lists++;
     p = ++Pass;
     while ((p & 1) == 0)
     {
         Merge(Stack); Lists--;
         p >>= 1;
     }
 }
 while (Lists > 1)
 {
     Merge(Stack); Lists--;
 }

Die verbliebene Liste auf dem Stack ist das sortierte Ergebnis.

Weitere Informationen

/Analyse?
/Implementation?
JavaArraysSortObjectSource

KategorieAlgorithmus KategorieSortierAlgorithmus