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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

Mergesort example.png

Im letzten Verschmelzungsschritt ist das Reißverschlussverfahren beim Verschmelzen (in der Abb. „Mischen:“) angedeutet. Blaue Pfeile verdeutlichen den Aufteilungsschritt, grüne Pfeile die Verschmelzungsschritte.

Es folgt ein Beispielcode analog zum obigen Abschnitt "Implementierung" für den rekursiven Sortieralgorithmus. Er teilt rekursiv absteigend die Eingabe in 2 kleinere Listen, bis diese trivialerweise sortiert sind, und verschmilzt sie auf dem rekursiven Rückweg, wodurch sie sortiert werden.

function merge_sort(list x)
  
    if length(x) ≤ 1 then
        return x      // Kurzes x ist trivialerweise sortiert.
    
    var l := empty list
    var r := empty list
    var i, nx := length(x)−1
    // Teile x in die zwei Hälften l und r ...
    for i := 0 to floor(nx/2) do
        append x[i] to l
    for i := floor(nx/2)+1 to nx do
        append x[i] to r
    // ... und sortiere beide (einzeln).
    l := merge_sort(l)
    r := merge_sort(r)
    // Verschmelze die sortierten Hälften.
    return merge(l, r)

Beispielcode zum Verschmelzen zweier sortierter Listen.

function merge(list l, list r)
    var y := empty list    // Ergebnisliste

    var nl := length(l)−1
    var nr := length(r)−1
    var i, il := 0
    for i := 0 to nl+nr do
        if il > nl then
            append r[iil] to y
            continue
        if il < inr then
            append l[il] to y
            il := il+1
            continue
        // Jetzt ist 0 ≤ ilnl und 0 ≤ iilnr.
        if l[il] ≤ r[iil] then
            append l[il] to y
            il := il+1
        else
            append r[iil] to y

    return y

Komplexität[Bearbeiten | Quelltext 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 .

Damit ist Mergesort hinsichtlich der Komplexität Quicksort grundsätzlich überlegen, da Quicksort (ohne besondere Vorkehrungen) ein Worst-Case-Verhalten von besitzt. Es benötigt jedoch zusätzlichen Speicherplatz (der Größenordnung ), ist also kein In-place-Verfahren.

Für die Laufzeit von Mergesort bei zu sortierenden Elementen gilt die Rekursionsformel

mit dem Rekursionsanfang .

Nach dem Master-Theorem kann die Rekursionsformel durch bzw. approximiert werden mit jeweils der Lösung (2. Fall des Mastertheorems, s. dort) .

Durchschnittliche und maximale Anzahl Vergleiche        

Sind die Längen der zu verschmelzenden und vorsortierten Folgen dann gilt für die Anzahl der erforderlichen Vergleiche fürs sortierende Verschmelzen

,

da erstens eine Folge komplett vor der anderen liegen kann, d. h. bzw. ist, oder zweitens (bzw. umgekehrt) ist, sodass die Elemente bis zum letzten Element in jeder Folge verglichen werden müssen. Dabei ist jeweils angenommen, dass das Vergleichen der zwei Folgen bei den Elementen mit niedrigem Index beginnt. Mit

sei die maximale Anzahl der Vergleiche fürs Verschmelzen bezeichnet. Für die maximale Anzahl an Vergleichen für einen ganzen Mergesort-Lauf von Elementen errechnet sich daraus

mit

ist die Folge A001855 in OEIS.

Für eine Gleichverteilung lässt sich auch die durchschnittliche Anzahl der Vergleiche genau berechnen, und zwar ist für

und für

Dabei ist die Anzahl der Vergleiche für die Anordnung

  ,

wobei für das letzte (das am höchsten sortierende) Element in der Folge steht, die (nicht von einem Element aus unterbrochenen) en zu gehören und (die auch fehlen können) entweder zu oder zu gehören. Der in den Summenformeln beigegebene Binomialkoeffizient zählt die verschiedenen Möglichkeiten für

Für die durchschnittliche Anzahl an Vergleichen für einen ganzen Mergesort-Lauf von Elementen errechnet sich daraus beispielsweise


2 1,0000 1 0,00000
3 2,6667 3 0,11111
4 4,6667 5 0,08333
6 9,8333 11 0,19444
8 15,733 17 0,15833
12 29,952 33 0,25397
16 45,689 49 0,20694
24 82,059 89 0,28922
32 121,50 129 0,23452
48 210,20 225 0,30839
64 305,05 321 0,24920
96 514,44 545 0,31838
128 736,13 769 0,25677
192 1218,9 1281 0,32348
256 1726,3 1793 0,26061
384 2819,8 2945 0,32606
512 3962,6 4097 0,26255
768 6405,6 6657 0,32736
1024 8947,2 9217 0,26352
1536 14345,0 14849 0,32801
2048 19940,0 20481 0,26401
3072 31760,0 32769 0,32833
4096 43974,0 45057 0,26426
6144 69662,0 71681 0,32849
8192 96139,0 98305 0,26438
12288 1,5161e5 155649 0,32857
16384 2,0866e5 212993 0,26444
24576 3,278e5 335873 0,32862
32768 4,5009e5 458753 0,26447
49152 7,0474e5 720897 0,32864
65536 9,6571e5 983041 0,26448
98304 1,5078e6 1540097 0,32865
131072 2,0625e6 2097153 0,26449
196608 3,2122e6 3276801 0,32865
262144 4,3871e6 4456449 0,26450
393216 6,8176e6 6946817 0,32865
524288 9,2985e6 9437185 0,26450
786432 1,4422e7 14680065 0,32865
1048576 1,9646e7 19922945 0,26450
1572864 3,0416e7 30932993 0,32866
2097152 4,1388e7 41943041 0,26450
3145728 6,3978e7 65011713 0,32866
4194304 8,6971e7 88080385 0,26450
6291456 1,3425e8 136314881 0,32866
8388608 1,8233e8 184549377 0,26450
12582912 2,8108e8 285212673 0,32866
16777216 3,8144e8 385875969 0,26450

und findet

Korrektheit und Terminierung[Bearbeiten | Quelltext 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 werden die sortierten Teillisten aus Rekursionstiefe korrekt sortiert.

Beweis: Sei o. B. d. A. die -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 -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 | Quelltext 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 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 | Quelltext 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 | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Donald E. Knuth: The Art of Computer Programming. Volume 3: Sorting and Searching. 2. Auflage. Addison-Wesley, 1998, S. 158.
  2. h2database/h2database. In: GitHub. Abgerufen am 1. September 2016.
  3. http://www.sgi.com/tech/stl/stable_sort.html stable_sort