MergeSort

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

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

Prinzip

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.

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 die selben 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.

Beispiel

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

Laufzeit

Mergesort ist im Gegensatz zu Quicksort stabil. Seine Komplexität beträgt in der Landau-Notation ausgedrückt O(n·log(n)). Damit ist Mergesort hinsichtlich der Komplexität Quicksort überlegen

(Quelle: de.wikipedia.org)

Implementierung

public class MergeSort {

  public static char[] arr = {'a', 'n', 'e', 'x', 'a', 'm', 'p', 'l', 'e'};

  public static void main(String[] args) {
    print(arr);
    print(mergesort(arr));
  }

  public static char[] mergesort(char[] aToSort){

    char[] aSorted = aToSort;

    if(aToSort.length>1){
      char[] aL = new char[aToSort.length/2];
      char[] aR = new char[aToSort.length-aL.length];

      for(int i=0; i<aL.length; i++){
        aL[i]=aToSort[i];
      }
      for(int i=0; i<aR.length; i++){
        aR[i]=aToSort[aToSort.length/2 + i];
      }

      aSorted = merge(mergesort(aL), mergesort(aR));
    }

    return aSorted;
  }

  public static char[] merge(char[] aL, char[] aR){
    char[] aM = new char[aL.length + aR.length];
    int pL = 0, pR = 0, pM = 0;

    while(pL<aL.length && pR<aR.length){
      if(aL[pL]<=aR[pR]){
        aM[pM]=aL[pL]; pL++;
      }
      else {
        aM[pM]=aR[pR]; pR++;
      }
      pM++;
    }

    while(pL<aL.length){
      aM[pM]=aL[pL]; pL++; pM++;
    }

    while(pR<aR.length){
      aM[pM]=aR[pR]; pR++; pM++;
    }

    return aM;
  }

  public static void print(char[] arr){
    for(int i=0; i<arr.length; i++){
      System.out.print(arr[i]+ " ");
    }
    System.out.println();
  }
}

Iteratives MergeSort für Listen

MergeSort kann recht einfach zum Sortieren von verketteten Listen eingesetzt werden. Wenn wir die rekursive Grundfunktion von oben betrachtet, dann erkennt man, dass zunächst in das Array 'hineinrekursiert' wird. Der Einfachheit halber nehmen wir mal an, dass dies glatt auf jeweils 2 Elemente geht.

Beispiel:

  5   1   7   8   6   3   9   2 

Rekursion (Aufruf 1.links)

  5   1   7   8   6   3   9   2 

Rekursion (Aufruf 1.links.links)

  5   1   7   8   6   3   9   2 

Sortierung

  1   5   7   8   6   3   9   2 

Rekursion (Aufruf 1.links.rechts)

  1   5   7   8   6   3   9   2 

Sortierung

  1   5   7   8   6   3   9   2 

Merge von 1.links.links mit 1.links.rechts nach 1.links

  1   5   7   8   6   3   9   2 

Rekursion (Aufruf 1.rechts)

  1   5   7   8   6   3   9   2 

Rekursion (Aufruf 1.rechts.links)

  1   5   7   8   6   3   9   2 

Sortierung

  1   5   7   8   3   6   9   2 

Rekursion (Aufruf 1.rechts.rechts)

  1   5   7   8   3   6   9   2 

Sortierung

  1   5   7   8   3   6   2   9 

Merge von 1.rechts.links mit 1.rechts.rechts nach 1.rechts

  1   5   7   8   2   3   6   9 

Merge von 1.links mit 1.rechts nach 1

  1   2   3   5   6   7   8   9 

Die Verarbeitung läuft strikt von links nach rechts, was für Listen optimal ist.

Algorithmus

 Solange Elemente in der Startliste sind
     Hole die ersten beiden und sortiere sie in eine neue Liste
     Pushe die neue Liste auf einen Listenstack
     Solange die beiden letzten Listen auf dem Stack gleich groß sind
         Merge die beiden letzten Listen zusammen, pushe das Ergebnis
 Merge alle restlichen Listen in Stackfolge zusammen

Schritt 1

  1 -> 5 

Schritt 2

  1 -> 5     7 -> 8 

Schritt 3

  1 -> 5 -> 7 -> 8 

Schritt 4

  1 -> 5 -> 7 -> 8     3 -> 6 

Schritt

  1 -> 5 -> 7 -> 8     3 -> 6     2 -> 9 

Schritt 6

  1 -> 5 -> 7 -> 8     2 -> 3 -> 6 -> 9 

Schritt 7

  1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8 -> 9 

Implementierung

» drucken: pdf | html