Merge sort ist ein divide-and-conquer, stabiler Sortieralgorithmus, der in garantierter O(n log n) Zeit läuft. Er teilt das Array in zwei Hälften, sortiert jede Hälfte rekursiv und führt dann die beiden sortierten Hälften zusammen.
Ein einzelnes Element ist bereits sortiert (Basisfall). Das Zusammenführen von zwei sortierten Listen ist linear, und wir führen log n Ebenen von Zusammenführungen durch.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
return merge(left, right)
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= keeps it stable
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:]); result.extend(b[j:])
return result
merge_sort([5, 2, 4, 1, 3]) # -> [1, 2, 3, 4, 5]
Ideal, wenn Sie Stabilität oder garantiertes O(n log n) benötigen, sowie für verlinkte Listen und Externe Sortierung riesiger Dateien. Der zusätzliche O(n) Speicher ist sein Hauptnachteil.
Merge Sort garantiert O(n log n) unabhängig von der Eingabe, im Gegensatz zu Quicksorts O(n²) schlechtestem Fall.
Seine Stabilität bewahrt die relative Reihenfolge gleicher Schlüssel, was beim Sortieren mit mehreren Schlüsseln wichtig ist.
Der Merge-Schritt ist eine wiederverwendbare Primitive, und die Divide-and-Conquer-Struktur ist ein Muster, das Sie überall wiederverwenden werden.