Merge Sort Demystified: Ein Anfängerleitfaden zum Divide-and-Conquer-Sortieren

Merge Sort wurde 1945 von John von Neumann eingeführt, hauptsächlich um die Effizienz beim Sortieren großer Datensätze zu verbessern. Von Neumanns Algorithmus zielte darauf ab, mithilfe der Divide-and-Conquer-Methode einen konsistenten und vorhersehbaren Sortierprozess bereitzustellen. Diese Strategie ermöglicht es Merge Sort, sowohl kleine als auch große Datensätze effektiv zu verarbeiten und garantiert in allen Fällen eine stabile Sortierung mit einer Zeitkomplexität von O(n log n).

Merge Sort verwendet den Teile-und-herrsche-Ansatz, der das Array in kleinere Unterarrays aufteilt, diese rekursiv sortiert und die sortierten Arrays dann wieder zusammenführt. Bei diesem Ansatz wird das Problem in überschaubare Abschnitte unterteilt, wobei jeder Abschnitt einzeln sortiert und effizient kombiniert wird. Dadurch funktioniert der Algorithmus auch bei großen Datensätzen gut, indem er den Sortieraufwand aufteilt.

Rekursion ist ein Prozess, bei dem sich eine Funktion selbst aufruft, um eine kleinere Version desselben Problems zu lösen. Das Problem wird so lange zerlegt, bis ein Punkt erreicht ist, an dem das Problem einfach genug ist, um direkt gelöst zu werden. Dies wird als Basisfall bezeichnet.

Unten finden Sie eine Implementierung von Merge Sort in JavaScript, die zeigt, wie das Array rekursiv aufgeteilt und zusammengeführt wird:

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] < right[0]) result.push(left.shift());
        else result.push(right.shift());
    }
    return result.concat(left, right);
}

Um besser zu verstehen, wie Merge Sort funktioniert, gehen wir den Prozess anhand des Arrays durch: [38, 27, 43, 3, 9, 82, 10]

Schritt 1: Rekursive Division (mergeSort-Funktion)
Das Array wird rekursiv in kleinere Unterarrays aufgeteilt, bis jedes Unterarray nur noch ein Element enthält. Dies geschieht durch die folgenden Zeilen in der mergeSort-Funktion:

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

Das stoppt unsere Rekursion.

So verläuft die rekursive Aufteilung:

• Erster Aufruf: mergeSort([38, 27, 43, 3, 9, 82, 10])
  • Das Array wird in der Mitte geteilt: [38, 27, 43] und [3, 9, 82, 10]

• Erste Hälfte:

  • mergeSort([38, 27, 43])
    • In der Mitte aufgeteilt: [38] und [27, 43]
  • mergeSort([27, 43])
    • Aufgeteilt in [27] und [43]
  • Die Unterarrays [38], [27] und [43] sind jetzt einzelne Elemente und können zusammengeführt werden.

• Zweite Hälfte:

  • mergeSort([3, 9, 82, 10])
    • In der Mitte aufgeteilt: [3, 9] und [82, 10]
  • mergeSort([3, 9])
    • Aufgeteilt in [3] und [9]
  • mergeSort([82, 10])
    • Aufgeteilt in [82] und [10]
  • Die Unterarrays [3], [9], [82] und [10] können jetzt zusammengeführt werden.

Schritt 2: Zusammenführen der sortierten Subarrays (Merge-Funktion)
Jetzt beginnen wir mit der Zusammenführung der Subarrays in sortierter Reihenfolge mithilfe der Zusammenführungsfunktion:

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] < right[0]) result.push(left.shift());
        else result.push(right.shift());
    }
    return result.concat(left, right);
}

So funktioniert der Zusammenführungsprozess:

Erste Zusammenführung (aus den Basisfällen):

• [27] und [43] zusammenführen → Ergebnis ist [27, 43]
• [38] mit [27, 43] zusammenführen → Ergebnis ist [27, 38, 43]

An diesem Punkt ist die linke Hälfte des Arrays vollständig zusammengeführt: [27, 38, 43].

Zweite Zusammenführung (aus den Basisfällen):

• [3] und [9] zusammenführen → Ergebnis ist [3, 9]
• [82] und [10] zusammenführen → Ergebnis ist [10, 82]
• Füge [3, 9] mit [10, 82] zusammen → Ergebnis ist [3, 9, 10, 82]

Jetzt ist die rechte Hälfte vollständig zusammengeführt: [3, 9, 10, 82].

Schritt 3: Endgültige Zusammenführung
Abschließend werden die beiden Hälften [27, 38, 43] und [3, 9, 10, 82] mit der Merge-Funktion zusammengeführt:

Vergleichen Sie 27 (links[0]) und 3 (rechts[0]). Seit 3 ​​< 27, addiere 3 zum Ergebnis.
Vergleichen Sie 27 und 9. Addieren Sie 9 zum Ergebnis.
Vergleichen Sie 27 und 10. Addieren Sie 10 zum Ergebnis.
Vergleichen Sie 27 und 82. Addieren Sie 27 zum Ergebnis.
Vergleichen Sie 38 und 82. Addieren Sie 38 zum Ergebnis.
Vergleichen Sie 43 und 82. Addieren Sie 43 zum Ergebnis.
Fügen Sie das verbleibende Element 82 aus dem rechten Array hinzu.
Das vollständig zusammengeführte und sortierte Array ist:
[3, 9, 10, 27, 38, 43, 82].

Zeitkomplexität: Bester, durchschnittlicher und schlechtester Fall: O(n log n)
Schauen wir es uns genauer an:

Teilen (O(log n)): Jedes Mal, wenn das Array in zwei Hälften geteilt wird, verringert sich die Größe des Problems. Da das Array bei jedem Schritt in zwei Hälften geteilt wird, ist die Häufigkeit, mit der Sie dies tun können, proportional zu log n. Wenn Sie beispielsweise 8 Elemente haben, können Sie diese dreimal halbieren (da log₂(8) = 3).

Zusammenführen (O(n)): Nach dem Teilen des Arrays führt der Algorithmus die kleineren Arrays der Reihe nach wieder zusammen. Das Zusammenführen zweier sortierter Arrays der Größe n dauert O(n) Zeit, da Sie jedes Element einmal vergleichen und kombinieren müssen.

Gesamtkomplexität (O(n log n)): Da die Division O(log n) Schritte erfordert und Sie bei jedem Schritt n Elemente zusammenführen, ist die gesamte Zeitkomplexität die Multiplikation dieser beiden: O(n log n).

Raumkomplexität: O(n)
Die Zusammenführungssortierung erfordert zusätzlichen Speicherplatz proportional zur Größe des Arrays, da temporäre Arrays zum Speichern der Elemente während der Zusammenführungsphase erforderlich sind.

Vergleich mit anderen Sortieralgorithmen:
QuickSort: Während QuickSort eine durchschnittliche Zeitkomplexität von O(n log n) hat, kann der schlimmste Fall O(n^2) sein. Merge Sort vermeidet dieses Worst-Case-Szenario, aber QuickSort ist im Allgemeinen schneller für die In-Memory-Sortierung, wenn Platz ein Problem ist.
Blasensortierung: Viel weniger effizient als Zusammenführungssortierung, mit einer zeitlichen Komplexität von O(n^2) für durchschnittliche und Worst-Case-Szenarien.

Nutzung in der realen Welt
Merge Sort wird häufig für die externe Sortierung verwendet, bei der große Datensätze von der Festplatte sortiert werden müssen, da es effizient mit Daten umgeht, die nicht in den Speicher passen. Es wird auch häufig in parallelen Computerumgebungen implementiert, in denen Subarrays unabhängig voneinander sortiert werden können und so die Vorteile der Multi-Core-Verarbeitung genutzt werden.

Darüber hinaus verlassen sich Bibliotheken und Sprachen wie Python (Timsort), Java und C (std::stable_sort) auf Variationen von Merge Sort, um Stabilität bei Sortiervorgängen zu gewährleisten, wodurch es sich besonders zum Sortieren von Objekten und komplexen Datenstrukturen eignet.

Fazit
Merge Sort ist aufgrund seiner Stabilität, konsistenten Leistung und Anpassungsfähigkeit zum Sortieren großer Datenmengen nach wie vor ein grundlegender Algorithmus sowohl in der theoretischen Informatik als auch in praktischen Anwendungen. Während andere Algorithmen wie QuickSort in bestimmten Situationen möglicherweise schneller arbeiten, ist Merge Sort aufgrund seiner garantierten O(n log n)-Zeitkomplexität und Vielseitigkeit für Umgebungen mit begrenztem Speicher und für die Aufrechterhaltung der Reihenfolge von Elementen mit gleichen Schlüsseln von unschätzbarem Wert. Seine Rolle in modernen Programmierbibliotheken stellt sicher, dass es in realen Anwendungen relevant bleibt.

Quellen:

1. Knuth, Donald E. The Art of Computer Programming, Bd. 3: Sortieren und Suchen. Addison-Wesley Professional, 1997, S. 158-160.
2. Cormen, Thomas H., et al. Einführung in Algorithmen. MIT Press, 2009, Kapitel 2 (Merge Sort), Kapitel 5 (Algorithmuskomplexität), Kapitel 7 (QuickSort).
3. Silberschatz, Abraham, et al. Datenbanksystemkonzepte. McGraw-Hill, 2010, Kapitel 13 (Externe Sortierung).
4. „Timsort.“ Python-Dokumentation, Python Software Foundation. Pythons Timsort
5. „Java Arrays.sort.“ Oracle-Dokumentation. Javas Arrays.sort()

Das obige ist der detaillierte Inhalt vonMerge Sort Demystified: Ein Anfängerleitfaden zum Divide-and-Conquer-Sortieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!