Tutorial zum Python-Merge-Sortieralgorithmus

Erfahren Sie, wie Sie Merge Sort in Python implementieren. Ein interaktives Schritt-für-Schritt-Beispiel der Sortierstrategie „Divide and Conquer“.

Versuchen Sie es im Editor

Übersicht

Merge Sort ist ein hocheffizienter Sortieralgorithmus, der eine Divide-and-Conquer-Strategie nutzt. Es zerlegt eine unsortierte Liste in kleinere Unterlisten, sortiert diese Unterlisten und führt sie dann wieder zusammen.

Der Algorithmus teilt das Array rekursiv in zwei Hälften, bis es Subarrays mit nur einem Element erreicht. Anschließend führt es die sortierten Unterarrays zusammen, indem es Elemente von jeder Seite vergleicht und sie in sortierter Reihenfolge anordnet. Dadurch wird eine optimale zeitliche Komplexität gewährleistet.

Unabhängig davon, ob das anfängliche Array sortiert, umgekehrt oder völlig zufällig ist, wird Merge Sort in O(n log n) Zeit ausgeführt. Es erfordert jedoch O(n) zusätzlichen Speicherplatz, um die Unterlisten während der Zusammenführungsphase zu speichern.

Code- und Ausführungsausgabe

Eine standardmäßige rekursive Implementierung des Merge Sort-Algorithmus in Python.

merge_sort.py

Versuchen Sie es im Editor

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
        
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Test dataset
data = [38, 27, 43, 3, 9, 82, 10]
print("Original List:", data)
sorted_data = merge_sort(data)
print("Sorted List:  ", sorted_data)

Terminal-Ausgabe

Original List: [38, 27, 43, 3, 9, 82, 10]
Sorted List:   [3, 9, 10, 27, 38, 43, 82]

Schrittweise Umsetzung

Sortieren verknüpfter Listen, bei denen die Knotenstruktur ein einfaches Zusammenführen ohne Kopieren ermöglicht
Externe Sortierroutinen für Dateien, die nicht vollständig in den System-RAM passen
Stabile Sortieranwendungen, bei denen übereinstimmende Schlüssel ihre ursprüngliche Reihenfolge beibehalten müssen

Häufig gestellte Fragen

Ist Merge Sort ein stabiler Sortieralgorithmus?

Ja, Merge Sort ist stabil. Beim Vergleich identischer Elemente wird das Element aus dem linken (ursprünglichen ersten) Subarray zuerst platziert, wobei seine ursprünglichen relativen Positionen erhalten bleiben.

Warum verwendet Python Timsort anstelle der reinen Merge-Sortierung?

Pythons integriertes „sorted()“ verwendet Timsort, einen Hybridalgorithmus, der Merge Sort und Insertion Sort kombiniert. Es optimiert reale Datenmuster durch die Identifizierung bereits sortierter Untersegmente und macht es so schneller als die reine Zusammenführungssortierung.