Mergesort

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Beispiel, wie Mergesort eine Liste sortiert. Die Listenelemente werden durch Punkte dargestellt. Die waagerechte Achse gibt an, wo sich ein Element in der Liste befindet, die senkrechte Achse gibt an, wie groß ein Element ist.

Mergesort (von englisch merge ‚verschmelzen‘ und sort ‚sortieren‘) ist ein stabiler Sortieralgorithmus, der nach dem Prinzip teile und herrsche (divide and conquer) arbeitet. Er wurde erstmals 1945 durch John von Neumann vorgestellt.[1]

Funktionsweise[Bearbeiten]

Mergesort betrachtet die zu sortierenden Daten als Liste und zerlegt sie in kleinere Listen, die jede für sich sortiert werden. Die sortierten kleinen Listen werden dann im Reißverschlussverfahren zu größeren Listen zusammengefügt (engl. (to) merge), bis wieder eine sortierte Gesamtliste erreicht ist. 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.[2] Verkettete Listen sind besonders geeignet zur Implementierung von Mergesort, dabei ergibt sich die in-place-Sortierung fast von selbst.

Veranschaulichung der Funktionsweise[Bearbeiten]

Funktionsweise

Das Bild veranschaulicht die drei wesentlichen Schritte eines Teile-und-herrsche-Verfahrens, wie sie im Rahmen von Mergesort umgesetzt werden. Der Teile-Schritt ist ersichtlich trivial (die Daten werden einfach in zwei Hälften aufgeteilt). Die wesentliche Arbeit wird beim Verschmelzen (merge) geleistet – daher rührt auch der Name des Algorithmus. Bei Quicksort ist hingegen der Teile-Schritt aufwendig und der Merge-Schritt einfacher (nämlich eine Konkatenierung).

Bei der Betrachtung des in der Grafik dargestellten Verfahrens sollte man sich allerdings bewusst machen, dass es sich hier nur um eine von mehreren Rekursionsebenen handelt. So könnte etwa die Sortierfunktion, welche die beiden Teile 1 und 2 sortieren soll, zu dem Ergebnis kommen, dass diese Teile immer noch zu groß für die Sortierung sind. Beide Teile würden dann wiederum aufgeteilt und der Sortierfunktion rekursiv übergeben, so dass eine weitere Rekursionsebene geöffnet wird, welche dieselben Schritte abarbeitet. Im Extremfall (der bei Mergesort sogar der Regelfall ist) wird das Aufteilen so weit fortgesetzt, bis die beiden Teile nur noch aus einzelnen Datenelementen bestehen.

Implementierung[Bearbeiten]

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[Bearbeiten]

Mergesort example.png

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[Bearbeiten]

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{n}_{\text{Aufwand, die beiden Teile zu verschmelzen}}

mit dem Rekursionsanfang T(1)=1.

Nach dem Master-Theorem kann die Rekursionsformel durch 2 T(\lfloor \tfrac{n}{2} \rfloor) + n bzw. 2 T(\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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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.[3]

Literatur[Bearbeiten]

  • Robert Sedgewick: Algorithmen. Pearson Studium, Februar 2002, ISBN 3827370329

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1.  Donald E. Knuth: The Art of Computer Programming. Volume 3: Sorting and Searching.. 2 Auflage. Addison-Wesley, 1998, S. 158.
  2. Eine Java Implementation einer stabilen in-place Variante von Merge Sort
  3. http://www.sgi.com/tech/stl/stable_sort.html stable_sort