Merge Sort

Merge Sort

Mergesort ist ein rekursiver, stabiler Sortieralgorithmus, der ähnlich wie Quicksort nach dem Prinzip Teile und herrsche (lat. Divide et impera, engl. Divide and Conquer) arbeitet. Er wurde erstmals 1945 durch John von Neumann vorgestellt.

Der zusätzliche Platzverbrauch des Mergesort-Algorithmus schwankt implementierungsabhängig. Der Algorithmus ist jedoch auf Arrays im Allgemeinen nicht in-place.

Inhaltsverzeichnis

Funktionsweise

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. Verkettete Listen sind besonders geeignet zur Implementierung von Mergesort, dabei ergibt sich die in-place-Sortierung fast von selbst.

Veranschaulichung der 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

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
       antworte merge(mergesort(linkeListe), mergesort(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

Mergesort ist im Gegensatz zu Quicksort stabil, wenn der Merge-Schritt geeignet implementiert wird. Seine Komplexität (Worst-, Best- und Average-Case-Verhalten) beträgt in der Landau-Notation ausgedrückt stets \mathcal{O}(n \log(n)). Damit ist Mergesort hinsichtlich der Komplexität Quicksort gewissermaßen überlegen, da Quicksort ein Worst-Case-Verhalten von \mathcal{O}(n^2) besitzt. Allerdings ist bei Quicksort bei vorherigem zufälligem Mischen die Wahrscheinlichkeit, dass dieser Fall auftritt, so gering, dass Quicksort in der Praxis bessere Ergebnisse erzielt.

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 ist ein temporäres Array derselben Länge des zu sortierenden Arrays als Zwischenspeicher nötig (somit arbeitet Mergesort nicht in-place, s.o.). Quicksort dagegen benötigt kein temporäres Array.

Literatur

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

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • merge sort — sąlajinis rikiavimas statusas T sritis informatika apibrėžtis Rikiavimo metodas, kai rikiuojamos sekos elementai skirstomi į grupes (rūšiuojami), o po to grupės paeiliui suliejamos į vieną seką. Procesas kartojamas keičiant skirstymo į grupes… …   Enciklopedinis kompiuterijos žodynas

  • Merge-Sort — Mergesort ist ein rekursiver, stabiler Sortieralgorithmus, der ähnlich wie Quicksort nach dem Prinzip Teile und herrsche (lat. Divide et impera, engl. Divide and Conquer) arbeitet. Er wurde erstmals 1945 durch John von Neumann vorgestellt. Der… …   Deutsch Wikipedia

  • Polyphase merge sort — A polyphase merge sort is an algorithm which decreases the number of runs at every iteration of the main loop by merging runs in pairs. Typically, a merge sort splits items into groups then recursively sorts each group. Once the groups are sorted …   Wikipedia

  • Merge algorithm — Merge algorithms are a family of algorithms that run sequentially over multiple sorted lists, typically producing more sorted lists as output. This is well suited for machines with tape drives. Use has declined due to large random access memories …   Wikipedia

  • Sort-merge join — The Sort Merge Join (also known as Merge Join) is an example of a join algorithm and is used in the implementation of a relational database management system. The basic problem of a join algorithm is to find, for each distinct value of the join… …   Wikipedia

  • Sort Merge Generator — The Sort Merge Generator was an application developed by Betty Holberton in 1951 for the Univac I and is one of the first examples of using a computer to create a computer program. The input to the application was a specification of files and the …   Wikipedia

  • sort — Synonyms and related words: adjust, ailing, alphabetize, analyze, appraise, arrange, array, assess, assort, batch, battery, blood, body, body build, bolt, brand, break down, breed, bulk, cast, catalog, catalogue, categorize, category, character,… …   Moby Thesaurus

  • UnShuffle sort — is a sort algorithm. IntroductionThe UnShuffle Sort is a distribution or merge sort which was developed by Art S. Kagel. UnShuffle is most efficient when sorting data which exhibits low entropy, in effect where the data is well ordered or… …   Wikipedia

  • Odd–even sort — Example of odd even transposition sort sorting a list of random numbers. Class Sorting algorithm Data structure Array Worst case performance …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”