Mergesort

Schon die Römer verwendeten das sogenannte "Teile und herrsche"-Prinzip – allerdings wurde es bei ihnen noch "Divide et impera!" genannt. Dahinter verstecken sich verschiedene Theorien. Eine davon erklärt das Teile-und-Herrsche-Prinzip als eine ursprüngliche Kriegsstrategie, die verwendet wurde, um größere Feinde oder Königreiche zu zerspalten und mit einer Eroberung wieder zu vereinen.

Nach genau diesem Prinzip funktioniert der Mergesort Sortieralgorithmus – nur natürlich ohne die Streitereien und den Krieg! Was genau dahintersteckt und wie der Algorithmus funktioniert, erfährst Du jetzt.

Mergesort Erklärung

Das Mergesort Sortierverfahren basiert auf dem sogenannten Divide and Conquer paradigm – also dem Teile-und-Herrsche-Prinzip. Was heißt das? Das Grundprinzip hinter dem Algorithmus ist es, eine Datenmenge immer wieder in zwei nahezu gleich große Teilmengen zu unterteilen. Das machst Du so lange, bis die Teilmengen nur noch jeweils ein Element enthalten. Dann wird das Ganze quasi in umgekehrter Richtung wieder zusammengeführt und dabei sortiert.

Mergesort Definition

Mergesort Algorithmus

Wie der Merge Sort Algorithmus funktioniert, lässt sich am besten an einem Beispiel erklären. Gegeben ist ein Array [5, 2, 8, 4, 9, 7, 1, 3, 6], das sortiert werden soll.

Schritt 1

Teile das gegebene Array zunächst so lange, bis die einzelnen Arrays eine Länge von 1 haben. Da es sich bei diesem Beispiel um eine ungerade Anzahl an Elementen handelt, sind die Teilbereiche logischerweise nicht alle gleich groß. Das sorgt dafür, dass lediglich die Werte 3 und 6 in einem vierten Schritt erneut unterteilt werden müssen. Im nächsten Schritt beginnst Du dann bei diesen beiden Elementen.

Schritt 2

Beginne nun damit, die einzelnen Arrays rückwärts wieder zusammenzuführen. In diesem Fall wird mit der 3 und der 6 begonnen.

Schritt 3

In der nächsten Zeile beginnst Du dann wieder von links damit, jeweils die zwei nebeneinander liegenden Arrays zusammenzuführen. Vergleiche dabei die Elemente miteinander, haben sie nicht die richtige Reihenfolge, sortierst Du sie zusätzlich – in diesem Beispiel wird aufsteigend sortiert.

Schritt 4

Führe nun wieder jeweils die benachbarten Arrays zu einem zusammen und sortiere dabei die Elemente, falls nötig.

Schritt 5

Im letzten Schritt müssen jetzt nur noch die beiden verbliebenen Arrays zusammengeführt und sortiert werden.

Tada – fertig ist Dein mit Merge Sort sortiertes Array!

Mergesort Vorgehensweise

Noch einmal kurz und knapp: Wie gehst Du beim Merge Sort Algorithmus vor?

• Teile die Datenmenge in zwei möglichst gleich große Hälften
• Wiederhole diesen Schritt, bis die Teilbereiche nur noch ein Element enthalten
• Führe nun die einzelnen Teilbereiche schrittweise wieder zusammen ("mergen") und sortiere sie dabei

Mergesort Komplexität

Wie sieht es mit der Komplexität beim Mergesort Verfahren aus? Unterschieden werden kann die Zeitkomplexität (Laufzeit) und die Platzkomplexität.

Mergesort Laufzeit

Die Laufzeit beträgt beim Mergesort in allen drei Anwendungsfällen (Best-Case, Average-Case, Worst-Case) O(n log n). Dabei macht es für die Laufzeit theoretisch keinen großen Unterschied, ob die Elemente bereits vorsortiert oder zufällig angeordnet sind.

Mergesort Platzkomplexität

Die Platzkomplexität beim Mergesort hat einen linearen Bedarf – sprich O(n). Das liegt daran, dass sich auch hier der zusätzlich benötige Speicherplatz verdoppelt, wenn die Eingabegröße verdoppelt wird. Der Algorithmus arbeitet in der Regel nicht in-place, da zusätzlicher Speicher benötigt wird.

Mergesort – Weitere Begrifflichkeiten

Im Folgenden werden noch ein paar weitere Begriffe rund um den Merge Sort Algorithmus geklärt. Dazu gehören:

• Stabilität
• Vergleichsbasiert
• Iterativ vs. rekursiv
• Parallelisierbarkeit

Mergesort Stabilität

Merge Sort ist ein stabiler Sortieralgorithmus. Der Punkt, an dem die ursprüngliche Reihenfolge verändert werden könnte, ist, wenn zwei Teilbereiche wieder zusammengeführt werden. Dabei wird geschaut, ob der größte Wert aus dem linken Teilbereich größer, kleiner oder gleich dem kleinsten Wert aus dem rechten Teilbereich ist. Wenn die Werte gleich sind, wird der linke zuerst kopiert – die Reihenfolge gleicher Elemente bleibt also immer erhalten.

Mergesort vergleichsbasiert

Merge Sort arbeitet vergleichsbasiert, da beim Zusammenführen der einzelnen Elemente immer zwei miteinander verglichen und sortiert werden.

Mergesort iterativ – rekursiv

Der Merge Sort Algorithmus wird meist rekursiv implementiert. Du kannst den Algorithmus aber auch iterativ verwenden.

Mergesort Parallelisierbarkeit

Ist Mergesort parallelisierbar? Die Antwort lautet: ja. Dafür gibt es zwei mögliche Ansätze: Entweder Du parallelisierst die Hauptmethode des Mergesort (merge()) oder Du parallelisierst die rekursiven Aufrufe des Mergesort.

Mergesort Vor- und Nachteile

Die Vor- und Nachteile des Mergesort findest Du in der folgenden Tabelle zusammengefasst:

Mergesort vs. Quicksort

Mergesort Beispiel

Für ein besseres Verständnis folgen nun noch ein paar weitere (Code-)Beispiele zum Mergesort.

Mergesort Anwendung

Die Anwendung von Mergesort erfolgt z. B. in folgenden Fällen:

• bei verketteten Listen
• wenn auf einem externen Speicher sortiert werden soll

Mergesort Pseudocode

Eine Möglichkeit zur Implementation von Mergesort wird Dir mit dem folgenden Pseudocode vorgestellt:

mergesort (Array array)

// Das Array wird beim Unterteilen in jeweils zwei gleich große Hälften (links und rechts) unterteilt
// Ist das Array <= 1 wird dieser Schritt beendet 

if array <= 1
do
    int mitte = array.length / 2
    int links -> i <= mitte - 1
    int rechts -> i >= array.length - mitte - 1
    links = mergesort(links)
    rechts = mergesort(rechts)
    return zusammenfuehren(links, rechts)

// Funktion zum Zusammenführen der Teilbereiche zu einem neuen Array

zusammenfuehren(links, rechts)
    int n
    int indexlinks = length(links) – 1
    int indexrechts = length(rechts) – 1
    int indexergebnis = 0

                 // Funktion wird durchgeführt, solange der linke und rechte Teilbereich nicht leer sind
        while indexlinks < links.length und indexrechts < rechts.length
                // Ist das erste Element des linken Arrays kleiner gleich dem ersten Element der rechten Seite
        if links[indexlinks] < rechts[indexrechts]
                        // dann füge das erste Element von links in das neue Array ein und entferne es aus dem alten
            neuesArray[indexergebnis] = links[indexlinks]
            indexlinks += 1
                // ansonsten füge das erste Element von rechts ins neue Array ein und entferne es aus dem alten
        else neuesArray[indexergebnis] = rechts[indexrechts]
            indexrechts += 1
            indexergebnis += 1
        // Solange das linke Array nicht leer ist
    while indexlinks < links.length
        // füge das erste Element aus dem linken Bereich in das neue Array ein und entferne es aus dem alten
        neuesArray[indexergebnis] = links[indexlinks]
        indexlinks += 1
        indexergebnis += 1
        // Solange das rechte Array nicht leer ist
    while (indexrechts < rechts.length)
        // füge das erste Element aus dem rechten Bereich in das neue Array ein und entferne es aus dem alten
        neuesArray[indexergebnis] = rechts[indexrechts]
        indexrechts += 1
        indexergebnis += 1
        // Gib das neue Array zurück
    return neuesArray