Mergesort

Mergesort: Erklärung

Der Mergesort gehört zu den stabilen Sortieralgorithmen. Er leitet sich im Allgemeinen vom englischen „merge“, also verschmelzen und „sort“, dem sortieren ab. Der Sinn dahinter ist einfach nur, dass der Algorithmus die vorhandenen Daten als eine gesamte Liste betrachtet, die er dann in kleinere Listen unterteilt. Man kann also sagen, er zerlegt ein Gesamtproblem in mehrere Teilprobleme und löst diese dann Stück für Stück. Im Endeffekt setzt er sie dann zum Schluss zu einer Gesamtlösung zusammen. Heißt also verallgemeinert, dass der Algorithmus nach dem Grundsatz teile- und herrsche arbeitet. Das Teile-und-herrsche-Verfahren (englisch divide and conquer) stellt in der Informatik ein Paradigma für den Entwurf eines effizienten Algorithmus dar.

direkt ins Video springen

Funktionsweise

Die Funktionsweise lässt sich ganz einfach in drei Schritten erklären:

1. Du hast eine Liste und zerlegst sie in zwei Hälften. Die Unterteilung setzt du solange fort, bis nur noch ein Element in einer Menge vorhanden ist.
2. Dann sortierst du alle Teilstücke für sich. Hier also alphabetisch von A nach Z.
3. Anschließend müssen die Hälften dann nach dem Suchkriterium zu einer Menge vermischt. Heißt also, dass wir hier auch wieder alphabetisch zusammenführen müssen. Zum Schluss haben wir dann unsere sortierte Liste.

Veranschaulichung der Funktionsweise

Das Bild illustriert dabei die drei wesentlichen Schritte des Teile-und-herrsche-Prinzips: Unterteilen, Sortierten und Verschmelzen.

Mergesort Beispiel

Aber schauen wir uns das doch lieber mal an einem ausführlicheren Beispiel an. Wir wollen dieses Array sortieren: [5] [2] [4] [8] [1] [9] [7] [3] [6]

Dafür zerteilen wir ihn also erstmal in der Mitte in zwei Teile. So haben wir auf der linken Seite vier und auf der rechten Seite fünf Elemente. Diese werden wieder halbiert, sodass wir drei Teile bestehend aus zwei Elementen haben und dann noch ein Teil bestehend aus drei Elementen. Wir halbieren nochmal und erhalten lauter einzelne Elemente, abgesehen von der 3 und der 6. Diese müssen noch einmal einzeln getrennt werden. Fertig.

direkt ins Video springen

Dann können wir nun also mit der Verschmelzung beginnen. Dabei werden immer zwei benachbarte Teile miteinander verbunden und dabei direkt sortiert. Wir packen also die 5 und die 2 zusammen und bringen sie direkt in die richtige Reihenfolge, also erst die 2, dann die 5. Das gleiche machen wir auch mit der 4 und der 8. Die sind schon richtig sortiert, also können wir uns das nächste Paar ansehen. Auch die 1 und die 9 sind sortiert. Dann fehlen noch die 7, die 3 und die 6. Da eine Zahl somit keinen Nachbar hat, verschmelzen wir erstmal nur die 3 und die 6 miteinander.

direkt ins Video springen

So, jetzt können wir wieder von links beginnen. Wir fügen 2 und 5 mit der 4 und der 8 zusammen. Dafür betrachten wir die jeweils ersten Elemente der Arrays miteinander. Die 2 ist kleiner als die 4 und wird ausgewählt. Dann wird die 5 mit der 4 verglichen und wir wählen die 4. Schließlich vergleichen wir noch die 5 mit der 8 und schreiben zuerst die 5 und dann die 8 in das neue Array.

Dasselbe machen wir nur mit der 7, der 3 und der 6. Zum Schluss müssen dann noch die letzten beiden Teile verschmolzen und geordnet werden und wir erhalten zum Schluss die sortierte Liste. Ziemlich einfach, oder?

Mergesort Pseudocode

Aber wie können wir den Algorithmus nun als verbalen Pseudocode darstellen? Der Algorithmus lässt sich in zwei Funktionen beschreiben, dafür wird zuerst einmal die Liste a eingegeben und in eine linke und rechte Hälfte halbiert. Für beide Seiten soll dann jeweils die Methode merge_sort ausgeführt werden (solange die Listen größer gleich 1 sind) und die verschmolzene sortierte Liste mit der Funktion verschmelzen zurückgegeben werden.

Mergesort Pseudocode – Unterteilen

Algorithmus:

merge_sort (Liste a)
    Falls die Liste a <= 1 ist, soll die Liste antworten – sonst
      soll die Liste in linke Liste l und rechte Liste r halbiert werden.
      l = merge_sort(l)
      r = merge_sort(r)
      zurückgeben verschmelze (l,r)

Pseudocode:

merge_sort (Liste a)
    if a <= 1
    do
      int mitte = a.lenght / 2
      int l -> i <= mitte – 1
      int r -> i >= array.length – mitte – 1
      l = merge_sort(l)
      r = merge_sort(r)
      return verschmelze(l,r)

Mergesort Pseudocode – Verschmelzen

Algorithmus:
Verschmelze (linkeListe l,rechteListe r)
  zu einer neuen Liste n,
  solange die linke und rechte Liste nicht leer ist.
      Falls das erste Element der linken Liste kleiner gleich
      das erste Element der rechten Liste ist,
  dann füge das erste Element der linken Liste in die neue
  Liste ein und entferne es aus der linken Liste l.
      Ansonsten soll das erste Element der rechten Liste in die
      neue Liste hinten eingefügt werden und aus der rechten
      Liste r entfernt werden
  Solange die linke Liste l nicht leer ist,
    füge erstes Element der linken Liste in die neue Liste ein
    und entferne es aus der linken Liste l.
  Solange die rechte Liste r nicht leer ist,
    füge erstes Element der rechten Liste in die neue Liste
    ein und entferne es aus der rechten Liste r
  neue Liste n zurückgeben.

Pseudocode:

verschmelze (l, r)
  int n
  int indexl = length(l) – 1
  int indexr = length(r) – 1
  int indergebnis = 0
    while indexl < l.length und indexr < r.length
    if l[indexl] < r[indexr]
  neul[indexergebnis] = l[indexl]
  indexl += 1
    else neul[indexergebnis] = r[indexr]
    indexr += 1
    indexergebnis += 1
  while indexl < l.length
    neul[indexergebnis] = l[indexl]
    indexl += 1
    indexergebnis += 1
  while (indexr < r.length)
    neul[indexergebnis] = r[indexr]
    indexr += 1
    indexergebnis += 1
  return neul

Implementierung: Mergesort Java

Hier kannst du einen beispielhaften Mergesort Java-Code sehen. Der Code ist dabei wie beim Pseudocode in zwei Methoden aufgeteilt – Unterteilen und Verschmelzen.

Java – Unterteilen

public static int[] merge_sort(int[] a)
{
  if (a.length > 1) {
    int mitte = (int)(a.length / 2);
    int[] l = new int[mitte];
      for (int i = 0; i <= mitte – 1; i++) {
        l[i] = a[i];

}

    int[] r = new int[a.length – mitte];
      for (int i = mitte; i <= a.length – 1; i++) {
        r[i – mitte] = a[i];
      }
  l = merge_sort(l);
  r = merge_sort(r);
  return verschmelze(l, r);
  }
  else
  {
  return a;
  }
}

Java – Verschmelzen

private static int[] verschmelze(int[] l, int[] r)
{
  int[] neul = new int[l.length + r.length];
  int indexl = 0;
  int indexr = 0;
  int indexergebnis = 0;
  while (indexl < l.length && indexr < r.length) {
    if (l[indexl] < r[indexr]) {
      neul[indexergebnis] = l[indexl];
      indexl += 1;
    } else {
      neul[indexergebnis] = r[indexr];
      indexr += 1;
    }
    indexergebnis += 1;
  }
  while (indexl < l.length) {
  neul[indexergebnis] = l[indexl];
  indexl += 1;
  indexergebnis += 1;
  }
  while (indexr < r.length) {
    neul[indexergebnis] = r[indexr];
    indexr += 1;
    indexergebnis += 1;
  }
return neul;
}

Implementierung: Mergesort Python

An dieser Stelle zeigen wir dir einen beispielhaften Mergesort Python-Code sehen. Der Code ist dabei wie beim Pseudocode in zwei Methoden aufgeteilt – Unterteilen und Verschmelzen.

Python – Teilen

def merge_sort(a):
  if len(a) < 2:
    return a
  mitte = len(a) // 2
  l = merge_sort(a[:mitte])
  r = merge_sort(a[mitte:])
  return verschmelze(l, r)
  r = merge_sort(a[mitte:])
  return verschmelze(l, r)

Python – Verschmelzen

def verschmelze(l, r):
  indexergebnis = []
  indexl = indexr = 0
  while indexl < len(l) and indexr < len(r):
    if left[indexl] < right[indexr]:
      indexergebnis.append(l[indexl])
      indexl += 1
    else:
      indexergebnis.append(r[indexr])
      indexr += 1
    indexergebnis += l[indexl:]
    indexergebnis += r[indexr:]
    return indexergebnis

Mergesort Laufzeit

Doch nun zur Mergesort Laufzeit. Bei diesem Sortieralgorithmus ist die Laufzeitkomplexität immer gleich. Sowohl im Worst-, Best- und Average-Case beträgt die Komplexität . Damit gehört er zu den schnellen Sortierverfahren. Der Aufwand setzt sich dabei so zusammen, dass erst die einzelnen Teile sortiert werden müssen und dann zusammen verschmolzen werden.

Grundsätzlich kann man sagen, dass der Algorithmus hinsichtlich seiner Komplexität dem Quicksort überlegen ist. Aber wenn du dir die Menge an Zwischenspeichern ansiehst, die bis zum Endergebnis benötigt werden, kannst du schon selbst erkennen, dass eine wahnsinnige große Menge an zusätzlichem Speicherplatz benötigt wird. Das muss natürlich in der Praxis beachtet werden.

2-Wege-Mergesort

Bezüglich dem Sortierverfahren kannst du auch immer wieder auf den Begriff Natural Mergesort oder natürliches 2-Wege-Mergesort treffen. Dabei handelt es sich um eine Erweiterung des Sortierverfahrens, die bereits vorhandene Teilfolgen, die vorsortiert sind, nutzt. Die vorsortierten Teilfolgen werden runs genannt. Diese müssen im ersten Durchgang bestimmt werden und gelten dann als Basis für den Mergevorgang.

Beispiel

Nehmen wir dafür einfach unser vorheriges Beispiel her, um uns das Ganze einmal genauer ansehen zu können.

Eingabeliste:      [5]          [2]          [4]         [8]          [1]         [9]         [7]         [3]         [6]

Runs:                   [5]          [2] – – – [4] – – – [8]         [1] – – – [9]        [7]          [3] – – – [6]

Merge:                [2] – – – [4] – – – [5] – – – [8]         [1] – – – [7] – – – [9]         [3] – – – [6]

Merge:                [1] – – – [2] – – – [4] – – – [5] – – – [7] – – – [8] – – – [9]         [3] – – – [6]

Merge:                [1] – – – [2] – – – [3] – – – [4] – – – [5] – – – [6] – – – [7] – – – [8] – – – [9]

Durch den natürlichen 2-Wege-Mergesort kann sich der Sortieralgorithmus bezüglich der Best Case Komplexität auf O(n) steigern.