Benutzer:MarcsTales/Mergesort

Animation der Sortierung einer Liste durch Mergesort

Mergesort (englisch to merge ‚verschmelzen‘ und to sort ‚sortieren‘) ist ein stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche arbeitet. Er wurde erstmals 1945 durch John von Neumann vorgestellt. Vorteil dieses Algorithmus ist seine Schnelligkeit, da sowohl durchschnittlicher als auch schlechtester Fall in der Komplexitätsklasse ${\mathcal {O}}(n\cdot \log(n))$ liegen.

Prinzip

Veranschaulichung der ersten Rekursionsebene

Enthält die zu sortierende Liste nur ein Element, ist sie offensichtlich bereits sortiert. Ansonsten wird sie halbiert und die beiden Teillisten jede für sich rekursiv sortiert. Die sortierten kleinen Listen werden dann im Reißverschlussverfahren zu größeren Listen verschmolzen, bis wieder eine sortierte Gesamtliste erreicht ist. Beim namensgebenden Verschmelzen (to merge) wird also die wesentliche Arbeit geleistet.

Implementierung

Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus, wobei liste die zu sortierenden Elemente enthält.

funktion mergesort(liste);
  falls (Größe von liste <= 1) dann antworte liste
  sonst
     halbiere die liste in linkeListe, rechteListe
     linkeListe = mergesort(linkeListe)
     rechteListe = mergesort(rechteListe)
     antworte merge(linkeListe, rechteListe)

funktion merge(linkeListe, rechteListe);
  neueListe
  solange (linkeListe und rechteListe nicht leer)
  |    falls (erstes Element der linkeListe <= erstes Element der rechteListe)
  |    dann füge erstes Element linkeListe in die neueListe hinten ein und entferne es aus linkeListe
  |    sonst füge erstes Element rechteListe in die neueListe hinten ein und entferne es aus rechteListe
  solange_ende
  solange (linkeListe nicht leer)
  |    füge erstes Element linkeListe in die neueListe hinten ein und entferne es aus linkeListe
  solange_ende
  solange (rechteListe nicht leer)
  |    füge erstes Element rechteListe in die neueListe hinten ein und entferne es aus rechteListe
  solange_ende
  antworte neueListe

Beispiel

Im letzten Merge-Schritt ist das Reißverschlussverfahren beim Mischen angedeutet. Blaue Pfeile verdeutlichen den Aufteilungs-Schritt, grüne Pfeile die Misch-Schritte.

Komplexität

Das Verfahren arbeitet bei Arrays in der Regel nicht in-place, es sind dafür aber (trickreiche) Implementierungen bekannt, in welchen die Teil-Arrays üblicherweise rekursiv zusammengeführt werden. Verkettete Listen sind besonders geeignet zur Implementierung von Mergesort, dabei ergibt sich die in-place-Sortierung fast von selbst.

Mergesort ist ein stabiles Sortierverfahren, vorausgesetzt der Merge-Schritt ist korrekt implementiert. Seine Komplexität beträgt im Worst-, Best- und Average-Case in Landau-Notation ausgedrückt stets ${\mathcal {O}}(n\cdot \log(n))$.

Damit ist Mergesort hinsichtlich der Komplexität Quicksort grundsätzlich überlegen, da Quicksort (ohne besondere Vorkehrungen) ein Worst-Case-Verhalten von ${\mathcal {O}}(n^{2})$ besitzt. Es benötigt jedoch zusätzlichen Speicherplatz, ist also kein In-place-Verfahren.

Für die Laufzeit $T(n)$ von Mergesort bei $n$ zu sortierenden Elementen gilt die Rekursionsformel

$T(n)=\underbrace {T(\lfloor {\tfrac {n}{2}}\rfloor )} _{\text{Aufwand, den einen Teil zu sortieren}}+\underbrace {T(\lceil {\tfrac {n}{2}}\rceil )} _{\text{Aufwand, den anderen Teil zu sortieren}}+\underbrace {{\mathcal {O}}(n)} _{\text{Aufwand, die beiden Teile zu verschmelzen}}$

mit dem Rekursionsanfang $T(1)=1$.

Nach dem Master-Theorem kann die Rekursionsformel durch $2T(\lfloor {\tfrac {n}{2}}\rfloor )+n$ bzw. $2T(\lceil {\tfrac {n}{2}}\rceil )+n$ approximiert werden mit jeweils der Lösung (2. Fall des Mastertheorems, s. dort) $T(n)={\mathcal {O}}(n\cdot \log(n))$.

Korrektheit und Terminierung

Der Rekursionsabbruch stellt die Terminierung von Mergesort offensichtlich sicher, so dass lediglich noch die Korrektheit gezeigt werden muss. Dies geschieht, indem wir folgende Behauptung beweisen:

Behauptung: In Rekursionstiefe $i$ werden die sortierten Teillisten aus Rekursionstiefe $i{+}1$ korrekt sortiert.

Beweis: Sei o. B. d. A. die $(i{+}1)$-te Rekursion die tiefste. Dann sind die Teillisten offensichtlich sortiert, da sie einelementig sind. Somit ist ein Teil der Behauptung schon mal gesichert. Nun werden diese sortierten Teillisten eine Rekursionsebene nach oben, also in die $i$-te Rekursion übergeben. Dort werden diese nach Konstruktion der Mischen-Prozedur von Mergesort korrekt sortiert. Somit ist unsere Behauptung erfüllt und die totale Korrektheit von Mergesort bewiesen.

Natural Mergesort

Natural Mergesort (natürliches Mergesort) ist eine Erweiterung von Mergesort, die bereits vorsortierte Teilfolgen, so genannte runs, innerhalb der zu sortierenden Startliste ausnutzt. Die Basis für den Mergevorgang bilden hier nicht die rekursiv oder iterativ gewonnenen Zweiergruppen, sondern die in einem ersten Durchgang zu bestimmenden runs:

Startliste    : 3--4--2--1--7--5--8--9--0--6
Runs bestimmen: 3--4  2  1--7  5--8--9  0--6
Merge         : 2--3--4  1--5--7--8--9  0--6
Merge         : 1--2--3--4--5--7--8--9  0--6
Merge         : 0--1--2--3--4--5--6--7--8--9

Diese Variante hat den Vorteil, dass sortierte Folgen „erkannt“ werden und die Komplexität im Best-Case ${\mathcal {O}}(n)$ beträgt. Average- und Worst-Case-Verhalten ändern sich hingegen nicht.

Außerdem eignet sich Mergesort gut für größere Datenmengen, die nicht mehr im Hauptspeicher gehalten werden können – es müssen jeweils nur beim Mischen in jeder Ebene zwei Listen vom externen Zwischenspeicher (z. B. Festplatte) gelesen und eine dorthin geschrieben werden. Eine Variante nutzt den verfügbaren Hauptspeicher besser aus (und minimiert Schreib-/Lesezugriffe auf der Festplatte), indem mehr als nur zwei Teil-Listen gleichzeitig vereinigt werden, und damit die Rekursionstiefe abnimmt.

Sonstiges

Da Mergesort die Startliste sowie alle Zwischenlisten sequenziell abarbeitet, eignet er sich besonders zur Sortierung von verketteten Listen. Für Arrays wird normalerweise ein temporäres Array derselben Länge des zu sortierenden Arrays als Zwischenspeicher verwendet (das heißt Mergesort arbeitet normalerweise nicht in-place, s. o.). Quicksort dagegen benötigt kein temporäres Array.

Die SGI-Implementierung der Standard Template Library (STL) verwendet den Mergesort als Algorithmus zur stabilen Sortierung.

Literatur

• Robert Sedgewick: Algorithmen. Pearson Studium, Februar 2002, ISBN 3-8273-7032-9

Weblinks

• Visualisierung und Tutorial für Mergesort, mit Darstellung der Rekursion
• Demonstration des Merge-Vorgangs (Java-Applet)

Einzelnachweise

Kategorie:Sortieralgorithmus