Mergesort und „Teile und herrsche“
Kurz gesagt: Mergesort teilt die Liste in Hälften bis auf einzelne Elemente und fügt sie der Reihe nach wieder zusammen: O(n log n) Vergleiche bei jeder Eingabe, auf Kosten von O(n) zusätzlichem Speicher.
Problem
„Nach Preis sortieren“ bei 100.000 Produkten
Der Onlineshop ist auf 100.000 Produkte gewachsen. Der Knopf „Nach Preis sortieren“ benutzt Insertionsort aus den einfachen Sortierverfahren.
Bei 1000 Produkten macht Insertionsort 256.555 Vergleiche, und die Seite öffnet sich sofort. Bei 100.000 sind es etwa 2,5 Milliarden Vergleiche. Die Produkte sind 100-mal mehr, und die Arbeit ist 10.000-mal größer: Insertionsort ist O(n²), weil jeder neue Preis mit allen Preisen davor verglichen werden kann.
Du brauchst einen Weg, bei dem doppelt so viele Produkte etwas mehr als doppelt so viel Arbeit ergeben.
Die Idee
Teile und herrsche
Wie sortieren zwei Personen einen Stapel von 1000 Rechnungen nach Betrag? Sie teilen ihn in zwei, jede sortiert ihre Hälfte, dann fügen sie zusammen: Sie schauen auf die oberste Rechnung beider Stapel und nehmen die kleinere. Zwei sortierte Stapel zusammenzufügen ist schnell: Jeder Vergleich bringt eine Rechnung an ihren Platz.
Und wie sortiert jede ihre Hälfte? Genauso: Sie teilt sie in zwei. Und so weiter, bis eine Rechnung übrig ist. Eine Rechnung ist schon sortiert.
Das ist Teile und herrsche (Divide and Conquer): Die Aufgabe wird in kleinere Aufgaben derselben Art zerlegt, sie werden mit derselben Methode gelöst, und ihre Antworten werden zusammengesetzt. Eine so gebaute Sortierung ist Mergesort.
Die Methode ruft sich selbst auf, also ist das Rekursion, wie in der Lektion „Rekursion“. Der Basisfall ist eine Liste mit einem Preis: Da gibt es nichts zu teilen.
Sieh es dir an
Bis auf einen Preis teilen und wieder zusammenfügen
merge_sort teilt und ruft sich für die zwei Hälften selbst auf. merge fügt zwei sortierte Teile zusammen. Sieh zu, wie die acht Preise bis auf einzelne hinuntergehen und die Merges sie auf dem Rückweg ordnen:
def merge_sort(prices): if len(prices) <= 1: return prices mid = len(prices) // 2 left = prices[:mid] right = prices[mid:] return merge(merge_sort(left), merge_sort(right))
def merge(left, right): merged = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: merged.append(left[i]) i += 1 else: merged.append(right[j]) j += 1 merged.extend(left[i:]) merged.extend(right[j:]) return mergedSchritt für Schritt, in Worten
- merge_sort bekommt 8 Preise aus dem Katalog, ungeordnet.
- mid = 4. Der Slice [:mid] legt zwei neue Listen an: die linke Hälfte [45, 12, 80, 33] und die rechte Hälfte [7, 61, 25, 50].
- Jede Hälfte ruft merge_sort für sich selbst auf und teilt wieder: 4 → 2 → 1.
- Ein Teil mit einem Preis ist schon sortiert. Das ist der Basisfall: Ab hier beginnen die Aufrufe zurückzukehren.
- merge fügt zwei sortierte Teile zusammen: Es vergleicht ihre ersten Preise und nimmt den kleineren. Für ein Paar ist das 1 Vergleich: 4 in der ganzen Reihe.
- Aus den Paaren werden Vierergruppen. Jeder Vergleich schickt einen Preis nach unten, also braucht eine Reihe nie mehr Vergleiche, als sie Preise hat: hier 6.
- Das letzte Zusammenfügen, [12, 33, 45, 80] mit [7, 25, 50, 61]. i und j zeigen auf den ersten noch nicht genommenen Preis jeder Seite: 7 Vergleiche, 7 Preise.
- Eine Seite ist zu Ende. Was auf der anderen übrig ist (80), ist schon sortiert und geht ohne Vergleich ans Ende.
- 3 Ebenen des Teilens (8 → 4 → 2 → 1), und auf jeder Ebene geht das Zusammenfügen einmal durch jeden Preis: 4 + 6 + 7 = 17 Vergleiche. Bei n Preisen gibt es log₂ n Ebenen, also ist die Arbeit etwa n · log₂ n.
prices = [45, 12, 80, 33, 7, 61, 25, 50]print(f"Vorher: {prices}")print(f"Nachher: {merge_sort(prices)}")Vorher: [45, 12, 80, 33, 7, 61, 25, 50]Nachher: [7, 12, 25, 33, 45, 50, 61, 80]prices[:mid] ist ein Slice: eine neue Liste mit den Elementen von 0 bis mid (ohne dieses). // teilt und rundet ab, also ist mid auch bei 9 Preisen 4.Die Idee
Warum es n · log n ist
Sieh, was jeder Teil kostet:
- Das Zusammenfügen ist O(n). Jeder Vergleich setzt einen Preis ins Ergebnis, und ist ein Teil leer, geht der Rest des anderen ohne Vergleich ans Ende. Zwei Teile mit zusammen n Preisen brauchen höchstens n − 1 Vergleiche.
- Es gibt log₂ n Ebenen. Jede Ebene halbiert: 8 Preise ergeben 3 Ebenen (8 → 4 → 2 → 1), 100.000 Preise ergeben 17. log₂ n ist „wie oft sich n bis auf 1 halbiert“.
- Auf jeder Ebene gehen die Merges einmal durch alle n Preise. Paare, Vierergruppen, Hälften: Die Gruppen unterscheiden sich von Ebene zu Ebene, aber zusammen sind es immer n.
Insgesamt: höchstens n · log₂ n Vergleiche. Bei 100.000 Preisen sind das unter 1.700.000. Bench zählt 1.536.292, etwa 1600-mal weniger als die 2,5 Milliarden von Insertionsort.
Probier es aus
Sage die Ausgabe voraus
Hier zählt merge seine Vergleiche. Die zwei Teile sind sortiert, und jeder Preis links ist kleiner als jeder Preis rechts:
comparisons = 0
def merge(left, right): global comparisons merged = [] i = j = 0 while i < len(left) and j < len(right): comparisons += 1 if left[i] <= right[j]: merged.append(left[i]) i += 1 else: merged.append(right[j]) j += 1 merged.extend(left[i:]) merged.extend(right[j:]) return merged
print(merge([10, 20, 30], [40, 50, 60]))print(f"Vergleiche: {comparisons}")Die drei Preise links kommen mit je einem Vergleich heraus: 10 gegen 40, 20 gegen 40, 30 gegen 40. Dann ist der linke Teil leer, und 40, 50 und 60 gehen ohne Vergleich ans Ende. Das Zusammenfügen von n Preisen braucht zwischen der Länge des kürzeren Teils (hier 3) und n − 1 (hier 5) Vergleiche. Nie mehr als n.
Sieh es dir an
Miss es: Mergesort gegen Insertionsort
Lass beide Algorithmen auf demselben Preiskatalog laufen. Gezählt werden Vergleiche. Insertionsort läuft bei 100.000 nicht wirklich (die Seite würde einfrieren): Bench schätzt ihn aus der Kurve.
- Insertion Sort
O(n²) - Merge Sort
O(n log n)
| Algorithmus | n = 10 | n = 1.000 | n = 10.000 | n = 100.000 |
|---|---|---|---|---|
| Insertion Sort | 32 | 256.555 | 24.738.716 | ≈ 2.473.871.600 |
| Merge Sort | 24 | 8.679 | 120.483 | 1.536.292 |
def merge_sort(prices): if len(prices) <= 1: return prices mid = len(prices) // 2 left = prices[:mid] right = prices[mid:] return merge(merge_sort(left), merge_sort(right))
def merge(left, right): merged = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: merged.append(left[i]) i += 1 else: merged.append(right[j]) j += 1 merged.extend(left[i:]) merged.extend(right[j:]) return mergedBei 10 Preisen sind die zwei fast gleich. Bei 1000 macht Mergesort 8.679 Vergleiche gegen 256.555. Von da an wächst der Abstand mit jeder Null: Die O(n²)-Kurve ist doppelt so steil.
Genauer, für Neugierige
Dieselben Zahlen in deiner Sprache. Der Katalog kommt aus einem kleinen Generator mit Seed, ist also bei jedem Lauf, in jeder Sprache und in Bench derselbe. Der Zähler steigt bei jedem Vergleich zweier Preise:
comparisons = 0
def catalog(n): prices = [] x = 2026 for _ in range(n): x = x * 48271 % 2147483647 prices.append(1 + x % 10000) return prices
def insertion_sort(prices): global comparisons for i in range(1, len(prices)): key = prices[i] j = i while j > 0: comparisons += 1 if prices[j - 1] <= key: break prices[j] = prices[j - 1] j -= 1 prices[j] = key
def merge_sort(prices): if len(prices) <= 1: return prices mid = len(prices) // 2 left = prices[:mid] right = prices[mid:] return merge(merge_sort(left), merge_sort(right))
def merge(left, right): global comparisons merged = [] i = j = 0 while i < len(left) and j < len(right): comparisons += 1 if left[i] <= right[j]: merged.append(left[i]) i += 1 else: merged.append(right[j]) j += 1 merged.extend(left[i:]) merged.extend(right[j:]) return merged
for n in [10, 1000]: comparisons = 0 insertion_sort(catalog(n)) print(f"insertion sort, n = {n}: {comparisons} Vergleiche")for n in [10, 1000, 100000]: comparisons = 0 merge_sort(catalog(n)) print(f"merge sort, n = {n}: {comparisons} Vergleiche")insertion sort, n = 10: 32 Vergleicheinsertion sort, n = 1000: 256555 Vergleichemerge sort, n = 10: 24 Vergleichemerge sort, n = 1000: 8679 Vergleichemerge sort, n = 100000: 1536292 VergleicheDie Idee
Der Preis: Speicher
Mergesort ist nicht umsonst. Insertionsort verschiebt die Preise in der Liste selbst und braucht keinen anderen Platz. Mergesort legt bei jeder Teilung neue Listen an, und merge schreibt das Ergebnis in ein weiteres. Der zusätzliche Speicher ist O(n): bei 100.000 Preisen noch einmal so viel Platz.
Der Aufrufstapel ist flach: ein Frame pro Ebene, etwa log₂ n. Bei 100.000 Preisen sind das 18 Frames.
Gleiche Preise bleiben in der Reihenfolge, in der sie kamen: Bei Gleichstand nimmt merge den linken (<=). Das nennt man Stabilität, und sie hat eine eigene Lektion, „Stabiles Sortieren und die eingebaute Sortierung“.
prices[:mid] immer eine neue Liste an. Dieser Mergesort ist also kurz, kopiert aber viel. Das eingebaute sorted ist TimSort, eine in C geschriebene Variante des Mergesort, und viel schneller.Probier es aus
Finde den Fehler
Ein Katalog mit acht Produkten geht hinein, und vier kommen heraus:
prices = [45, 12, 80, 33, 7, 61, 25, 50]print(f"Vorher: {prices}")print(f"Nachher: {merge_sort(prices)}")Vorher: [45, 12, 80, 33, 7, 61, 25, 50]Nachher: [33, 45, 50, 61]In welcher Zeile steckt der Fehler?
Wähle die Zeile mit dem Fehler.
Die rechte Hälfte beginnt bei mid + 1, und der Preis bei mid landet in keiner Hälfte. Jede Teilung verliert einen Preis: Bei 8 Preisen gehen 4 verloren. Der Compiler sagt nichts, und das Programm hält nicht an. Der linke Teil geht von 0 bis mid ohne mid, also muss der rechte genau bei mid beginnen.
Probier es aus
Fülle die Lücke
Die Schleife in merge hört auf, sobald ein Teil leer ist. Was kommt in die Lücke, damit der Rest des rechten Teils ans Ende geht?
def merge(left, right):
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[:])
return mergedj zeigt auf den ersten Preis rechts, der noch nicht genommen wurde. Alles ab j ist sortiert und größer als das bisher Genommene, also geht es ohne Vergleich ans Ende. Beginnst du stattdessen vom Anfang, kommen manche Preise doppelt hinein.
Übung
Zwei Lager, eine Preisliste
Löse die Aufgabe in deinem Editor.
Zwei Lager. Das Lager in Sofia und das Lager in Varna schicken ihre Preislisten, jede schon sortiert. Lies die zwei Zeilen und gib eine sortierte Preisliste für beide aus. Sortiere nicht noch einmal: Nutze merge aus der Lektion. Die Arbeit ist O(n), nicht O(n log n).
12 33 45 807 25 50 61 99Gesamt: 7 12 25 33 45 50 61 80 99Weitere Aufgaben
- Zählen. Füge
mergeeinen Zähler der Vergleiche hinzu und sortiere die acht Preise aus der Szene. Du solltest 17 bekommen. - Der teuerste zuerst. Ändere ein Zeichen, damit die Liste vom teuersten zum billigsten herauskommt.
- Ohne Rekursion. Füge die benachbarten einzelnen Preise zu Paaren zusammen, dann die Paare zu Vierergruppen, dann die Vierer. Das ist Bottom-up-Mergesort: dieselben Vergleiche, ohne Aufrufstapel.
Genauer
Zusammenfügen außerhalb des Sortierens
Das Zusammenfügen sortierter Listen ist älter als Mergesort: Lochkartenmaschinen fügten schon in den 1930er Jahren sortierte Kartenstapel zusammen. Heute taucht es überall auf, wo die Daten schon sortiert sind: in git, in Datenbanken, in Dateien, die größer sind als der Speicher.
Genauer, für Neugierige
Git. Git hält den Inhalt jedes Ordners (einen Baum) nach Dateinamen sortiert. Wenn es zwei Versionen vergleicht oder Zweige zusammenführt, geht es die zwei sortierten Listen nebeneinander durch, wie merge: Ein Name, der nur auf einer Seite steht, ist eine hinzugefügte oder gelöschte Datei, und gleiche Namen sind eine Datei auf beiden Seiten, die verglichen wird. Einen Ordner zu prüfen ist also O(n), nicht eine Suche für jede Datei in der anderen Liste. Den Text in einer Datei zusammenzuführen ist ein anderer Algorithmus (diff), zu dem wir im Modul „Dynamische Programmierung“ kommen.
Externes Sortieren. Die Logs der Seite für ein Jahr sind 50 GB, und der Speicher hat 8 GB. Die Sortierung liest 1 GB auf einmal, sortiert es im Speicher und schreibt es als sortierten Block auf die Platte. Dann fügt sie die Blöcke zusammen: Von jedem liest sie nur die erste Zeile, nimmt die kleinste und macht weiter. Der Speicher reicht für eine Zeile aus jedem Block. So sortiert der Befehl sort unter Linux große Dateien, und PostgreSQL schreibt Sort Method: external merge in den Abfrageplan, wenn die Sortierung nicht in seinen Speicher passt.
Das Mastertheorem als Intuition. Die Zeit von Mergesort schreibt man T(n) = 2 · T(n/2) + n: zwei Aufgaben halber Größe plus n für das Zusammenfügen. Zeichne es als Baum: Oben gibt es n Arbeit, auf der nächsten Ebene zweimal n/2, das ist wieder n, und so weiter über log₂ n Ebenen. Insgesamt n · log₂ n. Das Mastertheorem verallgemeinert genau diesen Vergleich: Schrumpft die Arbeit pro Ebene nach unten, entscheidet die oberste Ebene; wächst sie, entscheiden die Blätter; ist sie auf jeder Ebene gleich, multiplizierst du mit der Zahl der Ebenen. Die binäre Suche ist T(n) = T(n/2) + 1: 1 pro Ebene, log₂ n Ebenen, O(log n).
Die eingebaute Sortierung. In Python benutzen sorted und list.sort TimSort, eine Variante des Mergesort, die die schon sortierten Läufe in der Eingabe findet. Wie und warum, steht in der Lektion „Stabiles Sortieren und die eingebaute Sortierung“.
Test