Merge Sort: Teilen, sortieren, zusammenführen
Implementieren Sie Merge Sort rekursiv, verfolgen Sie den Divide-and-Conquer-Baum und erklären Sie, warum die Laufzeit in allen Fällen O(n log n) garantiert.
Merge Sort: Teilen, sortieren, zusammenführen ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Intuition hinter dem Teile-und-herrsche-Prinzip
Merge Sort ist ein klassischer Teile-und-herrsche-Algorithmus: Teilen Sie das Array in zwei Hälften, sortieren Sie beide Hälften rekursiv und führen Sie die beiden sortierten Hälften anschließend zu einem sortierten Ergebnis zusammen. Die entscheidende Erkenntnis ist, dass das Zusammenführen zweier sortierter Arrays O(n) benötigt – deutlich weniger, als sie von Grund auf zu sortieren. Diese Zerlegung erzeugt einen Rekursionsbaum mit log n Ebenen, wobei jede Ebene O(n) Arbeit für das Zusammenführen benötigt. Daraus ergibt sich die optimale Schranke für vergleichsbasierte Sortierverfahren von O(n log n).
# High-level merge sort structure
def merge_sort(arr):
# Base case: 0 or 1 element already sorted
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
# Conquer (merge)
return merge(left, right)
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]Der Merge-Schritt erklärt
Beim Zusammenführen zweier sortierter Arrays verwenden Sie zwei Zeiger, einen für jede Hälfte. Vergleichen Sie die jeweils vorderen Elemente, kopieren Sie das kleinere in die Ausgabe und bewegen Sie den entsprechenden Zeiger weiter. Wenn eine Hälfte vollständig verarbeitet ist, kopieren Sie den Rest der anderen Hälfte direkt. Dies benötigt O(n) Zeit und O(n) Speicher für das Ausgabe-Array. Der Merge-Schritt ist das algorithmische Herzstück von Merge Sort – verstehen Sie ihn gründlich.
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= preserves stability
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Append remaining elements
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge([1,3,5,7], [2,4,6,8]))
# [1, 2, 3, 4, 5, 6, 7, 8]Vollständige Implementierung von Merge Sort
Die Kombination aus Aufteilen und Mergen: Die rekursiven Aufrufe halbieren das Problem, bis nur noch einzelne Elemente übrig sind (die trivialerweise sortiert sind), anschließend führen die Merge-Aufrufe sie wieder zusammen. Auf jeder Ebene des Rekursionsbaums werden insgesamt dieselben n Elemente gemergt (verteilt auf mehrere Merge-Vorgänge). Die Rekursionstiefe beträgt log₂(n), wodurch sich eine Gesamtlaufzeit von O(n log n) und ein zusätzlicher Speicherbedarf von O(n) für die Merge-Ausgabearrays sowie eine Aufrufstapeltiefe von O(log n) ergeben.
def merge_sort_full(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_full(arr[:mid])
right = merge_sort_full(arr[mid:])
# Merge the two sorted halves
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:] + right[j:])
return merged
print(merge_sort_full([5,2,4,6,1,3,2,6]))
# [1, 2, 2, 3, 4, 5, 6, 6]Rekursionsbaum von Merge Sort
Visualisieren Sie den Rekursionsbaum von Merge Sort für n=8: Ebene 0 enthält ein Array mit 8 Elementen; Ebene 1 enthält zwei Arrays mit jeweils 4 Elementen; Ebene 2 enthält vier Arrays mit jeweils 2 Elementen; Ebene 3 enthält acht einzelne Elemente (die Basisfälle). Beim Zurücklaufen werden auf Ebene 3→2 insgesamt 8 Elemente gemergt, auf Ebene 2→1 ebenfalls 8 und auf Ebene 1→0 wiederum 8. Das ergibt 3 Ebenen × 8 Elemente = 24 Operationen ≈ 8 × log₂(8) = 24. Dies bestätigt O(n log n).
# Trace the tree depth
level_work = []
def merge_sort_traced(arr, depth=0):
if depth >= len(level_work):
level_work.append(0)
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_traced(arr[:mid], depth+1)
right = merge_sort_traced(arr[mid:], depth+1)
level_work[depth] += len(arr) # track merge work
merged = sorted(left + right) # simplified merge
return merged
merge_sort_traced(list(range(8, 0, -1)))
for d, work in enumerate(level_work):
print(f'Level {d}: {work} elements merged')In-Place-Merge-Sort
Der standardmäßige rekursive Merge Sort reserviert O(n) zusätzlichen Speicher für die Merge-Ausgabe. Es gibt zwar einen In-Place-Merge-Sort, dieser ist jedoch komplex und hat hohe konstante Faktoren – in Vorstellungsgesprächen wird er nur selten gefragt. Die häufige weiterführende Frage lautet: „Können Sie Merge Sort mit O(1) zusätzlichem Speicher implementieren?“ Die korrekte Antwort lautet: „Theoretisch ja, aber praktische Implementierungen verzichten entweder auf O(n) Speicher nicht oder erhöhen die Komplexität; Pythons Timsort verwendet O(n) Speicher für das Mergen.“
# Bottom-up merge sort: iterative, avoids recursion stack
def merge_sort_bottomup(arr):
n = len(arr)
width = 1
while width < n:
for i in range(0, n, 2 * width):
left = arr[i:i+width]
right = arr[i+width:i+2*width]
# Merge and put back
merged = []
a, b = 0, 0
while a < len(left) and b < len(right):
if left[a] <= right[b]: merged.append(left[a]); a+=1
else: merged.append(right[b]); b+=1
merged += left[a:] + right[b:]
arr[i:i+len(merged)] = merged
width *= 2
return arr
print(merge_sort_bottomup([5,2,4,6,1,3]))
# [1, 2, 3, 4, 5, 6]Merge Sort ist stabil
Merge Sort ist stabil: Gleiche Elemente aus der linken Hälfte erscheinen in der zusammengeführten Ausgabe immer vor gleichen Elementen aus der rechten Hälfte. Dies wird garantiert, indem beim Bevorzugen des linken Elements <= (nicht <) verwendet wird. Stabilität ist bei Sortierungen nach mehreren Schlüsseln wichtig. Pythons integrierte Funktionen sorted() und list.sort() verwenden Timsort, das ebenfalls stabil ist und O(n log n) benötigt, und sind daher die sichere Wahl für den gesamten Produktionscode.
# Demonstrating stability: sort (value, original_index) pairs
items = [(3,'A'), (1,'B'), (3,'C'), (2,'D')]
# Sort by value only
result = merge_sort_full(items) # won't work directly
# Use Python's stable sort:
result = sorted(items, key=lambda x: x[0])
print(result)
# [(1,'B'),(2,'D'),(3,'A'),(3,'C')]
# 'A' comes before 'C' for value=3 (stable order)K sortierte Arrays zusammenführen
Das Zusammenführen von k sortierten Arrays mit insgesamt n Elementen kann durch wiederholtes Zusammenführen von Paaren (wie in einem Turnierbaum) in O(n log k) Zeit erfolgen. Jede Merge-Ebene verarbeitet n Elemente, und es gibt log k Ebenen. Alternativ können Sie einen Min-Heap der Größe k verwenden: Legen Sie das jeweils kleinste noch verbleibende Element jedes Arrays hinein, entnehmen Sie das Minimum und fügen Sie das nächste Element aus diesem Array hinzu. Der Heap-Ansatz benötigt ebenfalls O(n log k), ist aber bei sehr großen k speichereffizienter.
import heapq
def merge_k_sorted(arrays):
result = []
heap = []
# Push first element from each array with array index
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
val, arr_i, elem_i = heapq.heappop(heap)
result.append(val)
if elem_i + 1 < len(arrays[arr_i]):
next_val = arrays[arr_i][elem_i + 1]
heapq.heappush(heap, (next_val, arr_i, elem_i+1))
return result
arrs = [[1,4,7],[2,5,8],[3,6,9]]
print(merge_k_sorted(arrs)) # [1,2,3,4,5,6,7,8,9]Inversionen mit Merge Sort zählen
Das Zählen von Inversionen (Paaren, für die a[i] > a[j] und i < j gilt) in O(n log n) verwendet einen modifizierten Merge Sort. Während des Merge-Schritts bildet ein Element aus dem rechten Teilarray, das kleiner als ein Element aus dem linken Teilarray ist, mit jedem noch verbleibenden Element im linken Teilarray eine Inversion. Addieren Sie in diesem Moment len(left) - i zum Zähler.
def count_inversions(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, l_inv = count_inversions(arr[:mid])
right, r_inv = count_inversions(arr[mid:])
merged = []
inversions = l_inv + r_inv
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
inversions += len(left) - i # all remaining left elements > right[j]
merged.extend(left[i:] + right[j:])
return merged, inversions
_, inv = count_inversions([3, 1, 2])
print(inv) # 2: (3,1) and (3,2)Merge Sort vs. Quick Sort
Merge Sort garantiert in allen Fällen O(n log n), ist stabil und die bessere Wahl für verkettete Listen und das externe Sortieren. Quick Sort erreicht im Durchschnitt O(n log n), im Worst Case jedoch O(n²), arbeitet in-place (mit O(log n) Stack-Speicher) und ist bei Arrays dank der Cache-Effizienz in der Praxis oft schneller. Pythons integrierte Sortierung verwendet Timsort (eine Variante von Merge Sort) – sie ist stets die richtige Standardwahl.
# Head-to-head complexity comparison:
# Algorithm | Best | Avg | Worst | Space | Stable
# Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Insertion sort| O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Merge sort | O(nlogn)| O(nlogn)| O(nlogn)| O(n) | Yes
# Quick sort | O(nlogn)| O(nlogn)| O(n^2) | O(logn)| No
# Heap sort | O(nlogn)| O(nlogn)| O(nlogn)| O(1) | No
print('Merge sort: stable, O(n log n) guaranteed, O(n) space')Externes Sortieren: Merge Sort im großen Maßstab
Merge Sort ist der Algorithmus hinter dem externen Sortieren (dem Sortieren von Daten, die nicht vollständig in den RAM passen). Die Daten werden in Blöcken eingelesen, jeder Block wird im Speicher sortiert und anschließend werden die Blöcke von der Festplatte gemergt. Der Merge-Schritt liest jeweils ein Element aus jedem sortierten Lauf und hält gleichzeitig nur O(k) Elemente im Speicher (eines pro Lauf). Deshalb wird Merge Sort in Datenbanken, Hadoop MapReduce und klassischen Bandsortieralgorithmen verwendet.
# Simulated external sort: sort in chunks then merge
def external_sort(data, chunk_size):
chunks = []
for i in range(0, len(data), chunk_size):
chunk = sorted(data[i:i+chunk_size]) # sort in-memory
chunks.append(chunk)
print(f'Created {len(chunks)} sorted chunks')
# Merge all chunks
import heapq
heap = [(c[0], i, 0) for i, c in enumerate(chunks) if c]
heapq.heapify(heap)
result = []
while heap:
val, ci, ei = heapq.heappop(heap)
result.append(val)
if ei + 1 < len(chunks[ci]):
heapq.heappush(heap, (chunks[ci][ei+1], ci, ei+1))
return result
print(external_sort(list(range(20,0,-1)), 5)[:10])Zusammenfassung und Tipps für Vorstellungsgespräche zu Merge Sort
In Vorstellungsgesprächen zeigt eine saubere Implementierung von Merge Sort, dass Sie Rekursion, den Merge-Schritt und das Teile-und-herrsche-Prinzip verstehen. Häufige weiterführende Fragen:
- Warum O(n log n) und nicht O(n²)? (log n Ebenen × n Arbeit pro Ebene)
- Ist der Algorithmus stabil? (Ja, verwenden Sie beim Mergen <=)
- Wie viel Speicher wird benötigt? (O(n) zusätzlicher Speicher + O(log n) Stack)
- Können Sie ihn iterativ implementieren? (Ja, mit Bottom-up-Merge-Sort)
- Wie würden Sie ihn auf eine verkettete Liste anwenden? (Einfacher als auf ein Array – keine O(n)-Kosten für Slices; verwenden Sie Slow-Fast-Zeiger, um den Mittelpunkt zu finden)
# One-shot merge sort for interview clarity:
def ms(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r, res, i, j = ms(a[:m]), ms(a[m:]), [], 0, 0
while i < len(l) and j < len(r):
if l[i] <= r[j]: res.append(l[i]); i+=1
else: res.append(r[j]); j+=1
return res + l[i:] + r[j:]
print(ms([5,2,4,6,1,3])) # [1,2,3,4,5,6]Wissenscheck
Überprüfen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Merge Sort teilt das Array am Mittelpunkt, sortiert jede Hälfte rekursiv und mergt die beiden sortierten Hälften in O(n) – dadurch ergibt sich über die log n Rekursionsebenen eine Gesamtlaufzeit von O(n log n), der Merge-Schritt verwendet <=, um bei Gleichstand das linke Element zu nehmen und dadurch Stabilität zu garantieren, und Merge Sort ist der bevorzugte Algorithmus für verkettete Listen, externes Sortieren und Situationen, in denen Stabilität erforderlich ist – während Quick Sort für Arrays im Speicher bevorzugt wird, wenn der Speicher begrenzt ist. Als Nächstes implementieren Sie Quick Sort und untersuchen Strategien zur Pivot-Auswahl.
Häufig gestellte Fragen
Ist die Lektion „Merge Sort: Teilen, sortieren, zusammenführen“ kostenlos?
Ja — der vollständige Text von „Merge Sort: Teilen, sortieren, zusammenführen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Merge Sort: Teilen, sortieren, zusammenführen“?
Implementieren Sie Merge Sort rekursiv, verfolgen Sie den Divide-and-Conquer-Baum und erklären Sie, warum die Laufzeit in allen Fällen O(n log n) garantiert. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Merge Sort: Teilen, sortieren, zusammenführen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Bubble Sort und Insertion Sort
- Merge Sort: Teilen, sortieren, zusammenführen
- Quick Sort und Pivot-Auswahl
- Nicht vergleichende Sortierverfahren und Pythons sort()