Python-Algorithmen

Mergesort (merge sort) in Python

In dieser Lektion implementierst du Mergesort nach dem Prinzip Teile und herrsche mit einer rekursiven Funktion.

  • Fortgeschritten
  • 3 Min. Lesezeit
  • 1 ausführbares Beispiel

Einführung

Das Problem

Einfache Sortierverfahren werden deutlich langsamer, wenn die Listen wachsen: Doppelt so viele Daten bedeuten viermal so viel Arbeit. Merge Sort teilt das Problem in kleinere Probleme, die leicht zu lösen sind. So wächst der Aufwand nur wenig schneller als die Datenmenge.

Stell es dir so vor

Merge Sort ist, als würdest du mit Freunden einen großen Stapel Klausuren sortieren. Du teilst den Stapel in zwei Hälften und gibst jede weiter, die anderen teilen ihre wieder, bis jeder nur noch ein Blatt hält. Dann führen immer zwei Leute ihre sortierten Stapel zusammen, indem sie stets das kleinere oberste Blatt nehmen, bis ein sortierter Stapel übrig ist.

Vom Klausurstapel zum Code
if len(values) <= 1:📄 Ein Blatt ist schon sortiert
merge_sort(values[:middle])✂️ Den Stapel teilen und jede Hälfte sortieren
left[left_index] <= right[right_index]🤝 Zusammenführen: das kleinere oberste Blatt nehmen
result + left[left_index:] + right[right_index:]📚 Den Rest des anderen Stapels anhängen
Bis auf einzelne Elemente teilen, dann sortierte Stapel wieder zusammenführen.
In einem Satz

Merge Sort teilt eine Liste in zwei Hälften, sortiert jede Hälfte rekursiv und führt die beiden sortierten Hälften zusammen. Er braucht O(n log n) Zeit.

Das Wichtigste

  1. if len(values) <= 1: return values ist der Basisfall, der die Rekursion beendet.
  2. merge_sort(values[:middle]) und merge_sort(values[middle:]) sortieren die beiden Hälften.
  3. Die while-Schleife nimmt den kleineren vorderen Wert aus left oder right, bis eine Liste leer ist.
  4. left[left_index:] und right[right_index:] hängen die restlichen Werte an, die schon sortiert sind.
  5. <= nimmt bei Gleichstand zuerst von links. So behalten gleiche Werte ihre ursprüngliche Reihenfolge.

Wann verwendet man das?

  • Große Daten verlässlich schnell sortieren, ohne schlechten Worst Case.
  • Verkettete Listen sortieren oder Daten, die nicht in den Speicher passen (externes Sortieren).
  • Divide and Conquer lernen, ein Muster, das in vielen Algorithmen vorkommt.

Wann du es nicht brauchst

  • Normaler Python-Code: sorted() nutzt schon Timsort, eine abgestimmte Mischung aus Merge Sort und Insertion Sort.
  • Sehr knapper Speicher: Merge Sort braucht zusätzlichen Platz für die zusammengeführten Listen.

Mergesort (merge sort) in Python visualisieren

O(n log n)

Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.

Beispielcode

Code ausführen →
main.py
def merge_sort(values):
    if len(values) <= 1:
        return values
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    result = []
    left_index = right_index = 0
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1
    return result + left[left_index:] + right[right_index:]

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
Run-Button für dieses Beispiel erstellen

Ergebnis der Ausführung

[3, 9, 10, 27, 38, 43, 82]

Erklärung des Codes

Die rekursive Funktion teilt die Liste, bis jeder Teil nur noch ein Element hat, denn eine Liste mit einem Element gilt immer als sortiert. Danach führt die while-Schleife die beiden Teillisten zusammen, indem sie immer das kleinere der beiden vorderen Elemente nimmt. Der Algorithmus läuft immer in O(n log n) Zeit und braucht O(n) zusätzlichen Speicher.

Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.

Übungen zur Vertiefung

Ändere den Code anhand der folgenden Vorschläge. Wenn du selbst etwas änderst und das Ergebnis beobachtest, verstehst du viel mehr, als wenn du den Code nur liest.

  1. Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
  2. Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
  3. Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Im Python-Compiler ausführen →

Häufige Fehler

Die Reste vergessen

Wenn eine Hälfte leer ist, geht der Rest der anderen Hälfte verloren.

Problem
return result
Lösung
return result + left[left_index:] + right[right_index:]

Lektion fertig?

Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges