Mergesort – Algorithmus, Quellcode, Zeitkomplexität

In diesem Artikel

• lernst Du, wie Mergesort (oft auch "Merge Sort") funktioniert,
• findest Du den Quellcode von Mergesort
• und du erfährst, wie man die Zeitkomplexität von Mergesort bestimmt, und zwar ohne komplizierte Mathematik.

Dies ist nach Quicksort der zweite effiziente Sortieralgorithmus aus der Artikelserie über Sortieralgorithmen.

Mergesort Algorithmus

Mergesort funktioniert nach dem „Teile-und-herrsche“-Prinzip („divide and conquer“):

Zunächst werden die zu sortierenden Elemente in zwei Hälften geteilt. Die entstandenen Sub-Arrays werden dann wieder geteilt – und wieder, bis Sub-Arrays der Länge 1 entstanden sind:

Nun werden in umgekehrter Richtung jeweils zwei Teil-Arrays so zusammengeführt ("gemerged"), dass jeweils ein sortiertes Array entsteht. Im letzten Schritt werden die zwei Hälften des ursprünglichen Arrays gemerged, so dass dieses letztendlich sortiert ist.

Wie genau zwei Teil-Arrays zu einem gemerged werden, wirst du in folgendem Beispiel sehen.

Mergesort Merge Beispiel

Das Mergen an sich funktioniert ganz einfach: Für beide Arrays wird ein Merge-Index festgelegt, der zunächst auf das erste Element des jeweiligen Arrays zeigt. Am einfachsten lässt sich das an einem Beispiel zeigen (die Pfeile stellen den jeweiligen Merge-Index dar):

Die Elemente, auf die die Merge-Zeiger zeigen, werden verglichen. Das kleinere von beiden (im Beispiel die 1) wird an ein neues Arrays angehängt und der Zeiger, der auf dieses Element gezeigt hat, wird um ein Feld nach rechts verschoben:

Jetzt werden erneut die Elemente über den Zeigern verglichen. Dieses mal ist die 2 kleiner als die 4, somit wird die 2 an das neue Array angehängt:

Jetzt liegen die Zeiger auf der 3 und der 4. Die 3 ist kleiner und wird an das Ziel-Array angehängt:

Jetzt ist die 4 am kleinsten:

Jetzt die 5:

Und im letzten Schritt bleibt die 6 übrig und wird an das neue Array angehängt:

Die zwei sortierten Teil-Arrays wurden durch das Mergen zu einem sortierten Gesamt-Array.

Mergesort Beispiel

Hier noch mal ein Beispiel für den Gesamt-Algorithmus. Sortiert werden soll das aus den anderen Teilen der Serie bekannte Array [3, 7, 1, 8, 2, 5, 9, 4, 6].

Dieses wird zunächst solange geteilt, bis Arrays der Länge 1 entstehen. Die Anordnung der Elemente ändert sich dabei nicht:

Jetzt werden die Teil-Arrays in umgekehrter Richtung nach dem oben beschriebenen Prinzip gemerged. Im ersten Schritt werden die 4 und die 6 zum Teil-Array [4, 6] zusammengefasst:

Als nächstes werden die 3 und die 7 zum Teil-Array [3, 7] gemerged, 1 und 8 zum Teil-Array [1, 8], die 2 und die 5 werden zu [2, 5]. Bis hierhin standen die gemergeten Elemente zufällig in der richtigen Reihenfolge zueinander und wurden daher nicht verschoben.

Das ändert sich jetzt: Die 9 wird mit dem Teil-Array [4, 6] gemerged – dabei wandert die 9 ans Ende des neuen Teil-Arrays [4, 6, 9]:

[3, 7] und [1, 8] werden nun zu [1, 3, 7, 8] gemerged. [2, 5] und [4, 6, 9] werden zu [2, 4, 5, 6, 9]:

Und im letzten Schritt werden die zwei Teil-Arrays [1, 3, 7, 8] und [2, 4, 5, 6, 9] zum Endergebnis zusammengeführt:

Am Ende erhalten wir das sortierte Array [1, 2, 3, 4, 5, 6, 7, 8, 9]. Das folgende Diagramm zeigt alle Merge-Schritte zusammengefasst in einer Übersicht:

Mergesort Java Quellcode

Im folgenden findest du die einfachste Implementierung von Mergesort.

Zunächst ruft die Methode sort() die Methode mergeSort() auf und übergibt dieser das Array sowie dessen Start- und Endpositionen.

mergeSort() prüft, ob es für ein Teil-Array der Länge 1 aufgerufen wurde und, wenn ja, gibt eine Kopie dieses Teil-Arrays zurück.

Anderfalls wird das Array geteilt, und mergeSort() wird rekursiv für beide Teile aufgerufen. Die beiden Aufrufe liefern jeweils ein sortiertes Array zurück. Diese werden anschließend durch Aufruf der merge()-Methode zusammengeführt, und mergeSort() gibt dieses zusammengeführte, sortierte Array zurück.

Abschließend kopiert die sort()-Methode das sortierte Array zurück in das Eingabe-Array. Man könnte das sortierte Array auch direkt zurückgeben – das wäre allerdings inkompatibel zum Test-Framework.

public class MergeSort {
  public void sort(int[] elements) {
    int length = elements.length;
    int[] sorted = mergeSort(elements, 0, length - 1);
    System.arraycopy(sorted, 0, elements, 0, length);
  }

  private int[] mergeSort(int[] elements, int left, int right) {
    // End of recursion reached?
    if (left == right) return new int[]{elements[left]};

    int middle = left + (right - left) / 2;
    int[] leftArray = mergeSort(elements, left, middle);
    int[] rightArray = mergeSort(elements, middle + 1, right);
    return merge(leftArray, rightArray);
  }

  int[] merge(int[] leftArray, int[] rightArray) {
    int leftLen = leftArray.length;
    int rightLen = rightArray.length;

    int[] target = new int[leftLen + rightLen];
    int targetPos = 0;
    int leftPos = 0;
    int rightPos = 0;

    // As long as both arrays contain elements...
    while (leftPos < leftLen && rightPos < rightLen) {
      // Which one is smaller?
      int leftValue = leftArray[leftPos];
      int rightValue = rightArray[rightPos];
      if (leftValue <= rightValue) {
        target[targetPos++] = leftValue;
        leftPos++;
      } else {
        target[targetPos++] = rightValue;
        rightPos++;
      }
    }
    // Copy the rest
    while (leftPos < leftLen) {
      target[targetPos++] = leftArray[leftPos++];
    }
    while (rightPos < rightLen) {
      target[targetPos++] = rightArray[rightPos++];
    }
    return target;
  }
}Code-Sprache: Java (java)

Den Quellcode findest Du hier im GitHub-Repository.

Mergesort Zeitkomplexität

(Die Begriffe „Zeitkomplexität“ und „O-Notation“ werden in diesem Artikel anhand von Beispielen und Diagrammen erklärt.)

Wir bezeichnen die Anzahl der Elemente mit n.

Da wir die (Sub-)Arrays immer wieder in zwei gleich große Teile aufteilen, benötigen wir bei einer Verdopplung der Anzahl der Elemente n nur eine einzige zusätzliche Stufe von Teilungen d. Folgendes Diagramm demonstriert, dass bei vier Elementen zwei Teilungsstufen benötigt werden und bei acht Elementen nur eine mehr:

Somit beträgt die Anzahl der Teilungsstufen log₂ n.

Auf jeder Merge-Stufe müssen wir insgesamt n Elemente zusammenführen (auf der ersten n × 1, auf der zweiten Stufe n/2 × 2, auf der dritten Stufe n/4 × 4, usw.):

Der Merge-Vorgang enthält keine verschachtelten Schleifen, erfolgt also mit linearem Aufwand: Bei Verdoppelung der Array-Größe verdoppelt sich auch der Merge-Aufwand. Der Gesamtaufwand ist daher auf allen Merge-Stufen gleich.

Wir haben also n Elemente mal log₂ n Teilungs- und Merge-Stufen. Damit gilt:

Die Zeitkomplexität von Mergesort beträgt: O(n log n)

Und zwar unabhängig davon, ob die Eingabeelemente vorsortiert sind oder nicht. Mergesort ist also für sortierte Eingabeelemente nicht schneller als für zufällig angeordnete.

Laufzeit des Java Mergesort-Beispiels

Genug der Theorie! Das Testprogramm UltimateTest misst die Laufzeit von Mergesort (und aller anderen Sortieralgorithmen dieser Artikelserie). Es geht dazu wie folgt vor:

• Sortiert werden Arrays der Länge 1.024, 2.048, 4.096, usw... bis maximal 536.870.912 (= 2²⁹) oder so lange, bis ein Sortiervorgang länger als 20 Sekunden dauert.
• Sortiert werden mit Zufallszahlen gefüllte Arrays, sowie aufsteigend und absteigend vorsortierte Zahlenfolgen.
• In zwei WarmUp-Runden wird dem HotSpot-Compiler ausreichend Zeit gegeben, den Code zu optimieren.

Die Tests werden solange wiederholt, bis der Prozess abgebrochen wird. Hier ist das Ergebnis für Mergesort nach 50 Wiederholungen (dies ist der Übersicht halber nur ein Auszug; das vollständige Ergebnis findest du hier):

Hier die Messwerte als Diagramm:

Es lässt sich sehr gut sehen:

• Die Laufzeit wächst in allen Fällen etwa linear mit der Anzahl der Elemente, entspricht also dem erwarteten quasi-linearen Aufwand – O(n log n).
• Für vorsortierte Elemente ist Mergesort etwa dreimal schneller als für unsortierte Elemente.
• Für absteigend vorsortierte Elemente benötigt Mergesort etwas mehr Zeit als für aufsteigend sortierte Elemente.

Wie lassen sich diese Unterschiede erklären?

Mit dem Programm CountOperations können wir die Anzahl der Operationen für die verschiedenen Fälle messen lassen. Die Anzahl der Schreiboperationen ist für alle Fälle gleich, da der Merge-Prozess – unabhängig von der Vorsortierung – alle Elemente der Teil-Arrays in ein neues Array kopiert.

Die Anzahl der Vergleiche unterscheidet sich jedoch; du findest sie in der folgenden Tabelle gegenübergestellt (das vollständige Ergebnis findest Du in der Datei CountOperations_Mergesort.log):

Laufzeitunterschied aufsteigend / absteigend sortierte Elemente

Der Unterschied zwischen aufsteigend und absteigend sortierten Elementen entspricht in etwa dem gemessenen Zeitunterschied. Der Grund für den Unterschied liegt in dieser Code-Zeile:

while (leftPos < leftLen && rightPos < rightLen)Code-Sprache: Java (java)

Bei aufsteigend sortierten Elementen werden zuerst alle Elemente des linken Teil-Arrays in das Ziel-Array kopiert, so dass leftPos < leftLen als erstes false ergibt und danach der rechte Term nicht mehr ausgewertet werden muss.

Bei absteigend sortierten Elementen werden zuerst alle Elemente des rechten Teil-Arrays kopiert, so dass rightPos < rightLen zuerst false ergibt. Da dieser Vergleich nach leftPos < leftLen ausgeführt wird, wird bei absteigend sortierten Elementen in jeder Merge-Runde einmal mehr der linke Vergleich leftPos < leftLen durchgeführt.

Würden wir die Zeile ändern in

while (rightPos < rightLen && leftPos < leftLen)Code-Sprache: Java (java)

... dann würde sich das Laufzeitverhältnis das Sortierens von aufsteigend zu absteigend vorsortierten Elementen entsprechend umkehren.

Laufzeitunterschied sortierte / unsortierte Elemente

Mergesort ist für vorsortierte Elemente etwa drei mal schneller als für unsortierte Elemente. Die Anzahl der Vergleichsoperationen unterscheidet sich allerdings nur um etwa ein Drittel.

Warum führt ein Drittel weniger Operationen zu dreimal schnellerer Abarbeitung?

Die Ursache liegt in der Sprungvorhersage (englisch „branch prediction“): Wenn die Elemente sortiert sind, dann sind die Resultate der Vergleiche in den Loop- und Branch-Statements

while (leftPos < leftLen && rightPos < rightLen)

und

if (leftValue <= rightValue)

bis zum Ende eines Merge-Vorgangs immer gleich. Somit kann die Befehls-Pipeline der CPU während des Mergens voll ausgenutzt werden.

Bei unsortierten Eingabedaten hingegen können die Resultate der Vergleiche nicht verlässlich vorhergesagt werden. Die Pipeline muss also ständig gelöscht und neu gefüllt werden.

Weitere Eigenschaften von Mergesort

Dieses Kapitel behandelt die Platzkomplexität von Mergesort, die Stabilität sowie die Parallelisierbarkeit.

Platzkomplexität von Mergesort

In der Merge-Phase werden Elemente aus zwei Teil-Arrays in ein neu erstelltes Ziel-Array kopiert. Im allerletzten Merge-Schritt ist das Ziel-Array genau so groß wie das zu sortierende Array. Wir haben also einen linearem Platzbedarf: Bei einem doppelt so großen Eingabe-Array verdoppelt sich auch der zusätzlich benötigte Speicherplatz. Es gilt also:

Die Platzkomplexität von Mergesort beträgt: O(n)

(Zur Erinnerung: Bei linearem Aufwand kann konstanter Platzbedarf für Hilfs- und Schleifenvariablen vernachlässigt werden.)

Dieser zusätzliche Speicherbedarf kann durch sogenannte In-Place-Verfahren umgangen werden; diese werden im Abschnitt "In-Place Mergesort" behandelt.

Stabilität von Mergesort

In der Merge-Phase entscheiden wir mittels if (leftValue <= rightValue), ob das nächste Element aus dem linken oder rechten Teil-Array in das Ziel-Array kopiert wird. Wenn linker und rechter Wert gleich sind, wird also zuerst der linke kopiert und dann der rechte. Somit bleibt die Reihenfolge gleicher Elemente zueinander immer unverändert.

Mergesort ist demzufolge ein stabiles Sortierverfahren.

Parallelisierbarkeit von Mergesort

Es gibt grundsätzlich zwei Ansätze, um Mergesort zu parallelisieren:

• Rekursive Aufrufe von mergeSort() können parallel ausgeführt werden; hierbei können allerdings heutige Mehrkern-CPUs in den letzten Merge-Stufen nicht voll ausgenutzt werden.
• Die merge()-Methode selbst kann parallelisiert werden.

Weiterführende Informationen dazu findest du im Mergesort-Artikel von Wikipedia.

In-Place Mergesort

Im Abschnitt "Platzkomplexität" haben wir festgestellt, dass Mergesort einen zusätzlichen Platzbedarf in der Größenordnung O(n) hat.

Es gibt verschiedene Ansätze, um den Merge-Vorgang ohne zusätzlichen Speicher (also "in place") auskommen zu lassen.

Ein Ansatz ist folgender:

• Wenn das Element über dem linken Merge-Zeiger kleiner oder gleich dem Element über dem rechten Merge-Zeiger ist, wird der linke Merge-Zeiger um ein Feld nach rechts verschoben.
• Andernfalls werden alle Element vom ersten Zeiger bis zu, aber ausschließlich dem zweiten Zeiger um ein Feld nach rechts geschoben und das rechte Element auf den freigewordenen Platz gesetzt. Danach werden beide Zeiger um ein Feld nach rechts verschoben, ebenso die Endposition des linken Teil-Arrays.

In-Place Mergesort – Beispiel

Das folgende Beispiel zeigt diesen In-Place-Merge-Algorithmus am Beispiel von oben – gemerged werden sollen die Teil-Arrays [2, 3, 5] und [1, 4, 6].

Das linke Teil-Array ist gelb eingefärbt, das rechte orange und die fertig gemergten Elemente blau.

Im ersten Schritt tritt gleich der zweite Fall ein: Das rechte Element (die 1) ist kleiner als das linke. Es werden alle Elemente des linken Teil-Arrays um ein Feld nach rechts geschoben und das rechte Element wird an den Anfang gesetzt:

Im zweiten Schritt ist das linke Element (die 2) kleiner, daher wird lediglich der linke Suchzeiger ein Feld nach rechts verschoben:

Im dritten Schritt ist wieder das linke Element (die 3) kleiner, es wird also wieder der linke Suchzeiger verschoben:

Im vierten Schritt ist das rechte Element (die 4) kleiner als das linke. Der verbleibende Teil des linken Bereichs (nur noch die 5) wird also um ein Feld nach rechts geschoben und das rechte Element auf den freien Platz gesetzt:

Im fünften Schritt ist das linke Element (die 5) kleiner. Der linke Suchzeiger wird um eine Position nach rechts geschoben und hat damit das Ende des linken Bereichs erreicht:

Der In-Place-Merge-Vorgang ist damit abgeschlossen.

In-Place Mergesort – Zeitkomplexität

Wir haben die Merge-Phase jetzt zwar ohne zusätzlichen Speicherbedarf ausgeführt – allerdings haben wir uns dies teuer erkauft: Durch die zwei verschachtelten Schleifen hat die Merge-Phase nun eine Zeitkomplexität im average und worst case von O(n²) – statt vorher O(n).

Die Gesamt-Komplexität des Sortierverfahrens ist damit O(n² log n) – statt O(n log n). Der Algorithmus ist somit nicht mehr effizient.

Lediglich im best case, wenn die Zahlen vorab aufsteigend sortiert sind, bleibt die Zeitkomplexität innerhalb der Merge-Phase O(n) und die des Gesamt-Algorithmus O(n log n). Der Grund dafür ist, dass in diesem Fall die innere Schleife, die die Elemente des linken Teilarrays nach rechts verschiebt, nie ausgeführt wird.

In-Place Mergesort – Quellcode

Hier ist der Quellcode der merge()-Methode von In-Place Mergesort:

void merge(int[] elements, int leftPos, int rightPos, int rightEnd) {
  int leftEnd = rightPos - 1;

  while (leftPos <= leftEnd && rightPos <= rightEnd) {
    // Which one is smaller?
    int leftValue = elements[leftPos];
    int rightValue = elements[rightPos];
    if (leftValue <= rightValue) {
      leftPos++;
    } else {
      // Move all the elements from leftPos to excluding rightPos one field
      // to the right
      int movePos = rightPos;
      while (movePos > leftPos) {
        elements[movePos] = elements[movePos - 1];
        movePos--;
      }
      elements[leftPos] = rightValue;
      leftPos++;
      leftEnd++;
      rightPos++;
    }
  }
}Code-Sprache: Java (java)

Den vollständigen Quellcode findest du in der Klasse InPlaceMergeSort im GitHub-Repository.

Effiziente In-Place-Merge-Verfahren

Es gibt auch effizientere In-Place-Mergeverfahren, die eine Zeitkomplexität von O(n log n) erreichen und damit eine Gesamt-Zeitkomplexität von O(n (log n)²), diese sind jedoch sehr komplex, so dass ich sie hier nicht weiter behandeln werde.

Natural Mergesort

Natural Mergesort ist eine Optimierung von Mergesort: Es identifiziert vorsortierte Bereiche ("runs") in den Eingabedaten und merged diese jeweils miteinander. So wird das unnötige weitere Teilen und Mergen vorsortierter Teilfolgen vermieden. Komplett aufsteigend sortierte Eingabeelemente werden dementsprechend in der Größenordnung O(n) sortiert.

Je nach Implementierung werden auch absteigend sortierte Teilfolgen ("descending runs") erkannt und in umgekehrter Richtung gemerged. Diese Varianten erreichen auch für komplett absteigend sortierte Eingabedaten O(n).

Natural Mergesort – Beispiel

Die folgende Grafik zeigt Natural Mergesort am Beispiel unserer Zahlenfolge [3, 7, 1, 8, 2, 5, 9, 4, 6]. Im ersten Schritt werden die "runs" identifiziert. In den folgenden Schritten werden diese gemerged:

Natural Mergesort – Quellcode

Der folgende Quellcode zeigt eine einfache Implementierung, bei der nur aufsteigend sortierte Bereiche identifiziert und gemerged werden:

public void sort(int[] elements) {
  int numElements = elements.length;

  int[] tmp = new int[numElements];
  int[] starts = new int[numElements + 1];

  // Step 1: identify runs
  int runCount = 0;
  starts[0] = 0;
  for (int i = 1; i <= numElements; i++) {
    if (i == numElements || elements[i] < elements[i - 1]) {
      starts[++runCount] = i;
    }
  }

  // Step 2: merge runs, until only 1 run is left
  int[] from = elements;
  int[] to = tmp;

  while (runCount > 1) {
    int newRunCount = 0;

    // Merge two runs each
    for (int i = 0; i < runCount - 1; i += 2) {
      merge(from, to, starts[i], starts[i + 1], starts[i + 2]);
      starts[newRunCount++] = starts[i];
    }

    // Odd number of runs? Copy the last one
    if (runCount % 2 == 1) {
      int lastStart = starts[runCount - 1];
      System.arraycopy(from, lastStart, to, lastStart,
            numElements - lastStart);
      starts[newRunCount++] = lastStart;
    }

    // Prepare for next round...
    starts[newRunCount] = numElements;
    runCount = newRunCount;

    // Swap "from" and "to" arrays
    int[] help = from;
    from = to;
    to = help;
  }

  // If final run is not in "elements", copy it there
  if (from != elements) {
    System.arraycopy(from, 0, elements, 0, numElements);
  }
}Code-Sprache: Java (java)

Die Signatur der merge()-Methode unterscheidet sich hier wie folgt vom Beispiel oben:

• Anstatt von Teil-Arrays wird hier das gesamte Ursprungs-Arrays sowie Positionsangaben der zu mergenden Bereiche übergeben.
• Anstatt ein neues Array zurückzugeben, wird auch das Ziel-Array zum Befüllen an die Methode übergeben.

Der eigentliche Merge-Algorithmus bleibt der gleiche.

Den vollständigen Quellcode einschließlich der merge()-Methode findest du in der Klasse NaturalMergeSort im GitHub-Repository.

Timsort

Das von Tim Peters entwickelte Timsort ist eine hoch optimierte Weiterentwicklung von Natural Mergesort, bei der unter anderem (Teil-)Arrays bis zu einer bestimmten Größe mit Insertion Sort sortiert werden.

Timsort ist der Standard-Sortieralgorithmus in Python. Im JDK wird es für alle nicht-primitiven Objekte verwendet, also in den folgenden Methoden:

• Collections.sort​(List<T> list)
• Collections.sort​(List<T> list, Comparator<? super T> c)
• List.sort(Comparator<? super E> c)
• Arrays.sort(T[] a, Comparator<? super T> c)
• Arrays.sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)

Mergesort vs. Quicksort

Wie schlägt sich Mergesort im Vergleich zu den im vorangegangenen Artikel behandelten Quicksort?

Das folgende Diagramm zeigt die Laufzeiten für unsortierte und aufsteigend sortierte Eingabedaten. Absteigend vorsortierte Elemente werden von beiden Algorithmen minimal langsamer verarbeitet als aufsteigend vorsortierte, ich habe sie deshalb der Übersichtlichkeit halber nicht in das Diagramm eingetragen.

Quicksort ist für eine Viertelmilliarde unsortierte Elemente etwa 50 % schneller als Mergesort. Für vorsortierte Elemente ist es sogar vier mal so schnell.

Der Grund liegt ganz einfach darin, dass beim Mergen immer alle Elemente kopiert werden. Bei Quicksort hingegen werden nur diejenigen Elemente verschoben, die sich in der falschen Partition befinden.

Mergesort hat gegenüber Quicksort den Vorteil, dass auch im worst case die Zeitkomplexität O(n log n) nicht überschritten wird und dass es stabil ist. Diese Vorteile erkauft man sich durch schlechtere Performance und einen zusätzlichen Platzbedarf in der Größenordnung O(n).

Zusamenfassung

Mergesort ist ein effizienter, stabiler Sortieralgorithmus mit einer Zeitkomplexität von O(n log n) im best, average und worst case.

Mergesort hat in seiner Standardimplementierung eine zusätzliche Platzkomplexität von O(n) – diese kann durch eine In-Place-Sortierung umgangen werden, welche allerdings entweder sehr komplex ist oder die Zeitkomplexität des Algorithmus gravierend verschlechtert.

Die JDK-Methoden Collections.sort(), List.sort() und Arrays.sort() (letzteres für alle nicht-primitiven Objekte) verwenden Timsort: ein optimiertes Natural Mergesort, wobei vorsortierte Bereiche in den Eingabedaten erkannt und nicht weiter geteilt werden.

Wenn dir der Artikel gefallen hat, teile ihn gerne über einen der Share-Buttons am Ende. Möchtest du per E-Mail informiert werden, wenn ich einen neuen Artikel veröffentliche? Dann klicke hier, um dich in den HappyCoders-E-Mail-Verteiler einzutragen