Mergesort (merge sort) in Python
In dieser Lektion implementierst du Mergesort nach dem Prinzip Teile und herrsche mit einer rekursiven Funktion.
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.
if len(values) <= 1:📄 Ein Blatt ist schon sortiertmerge_sort(values[:middle])✂️ Den Stapel teilen und jede Hälfte sortierenleft[left_index] <= right[right_index]🤝 Zusammenführen: das kleinere oberste Blatt nehmenresult + left[left_index:] + right[right_index:]📚 Den Rest des anderen Stapels anhängenMerge 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
if len(values) <= 1: return valuesist der Basisfall, der die Rekursion beendet.merge_sort(values[:middle])undmerge_sort(values[middle:])sortieren die beiden Hälften.- Die
while-Schleife nimmt den kleineren vorderen Wert ausleftoderright, bis eine Liste leer ist. left[left_index:]undright[right_index:]hängen die restlichen Werte an, die schon sortiert sind.<=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
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]))
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.
- Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
- Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
- Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Häufige Fehler
Die Reste vergessen
Wenn eine Hälfte leer ist, geht der Rest der anderen Hälfte verloren.
return result
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