Merge Sort in Python
Merge Sort teilt die Eingabe rekursiv und führt sortierte Teillisten wieder zusammen.
Was ist Merge Sort?
Merge Sort teilt die Eingabe rekursiv und führt sortierte Teillisten wieder zusammen.
Sortiere Daten mit dem Teile-und-herrsche-Prinzip.
Wann wird dieser Ansatz verwendet?
- Algorithmen und Datenstrukturen anhand von ausführbarem Code verstehen.
- Die einzelnen Verarbeitungsschritte und Randfälle nachvollziehen.
- Laufzeit und Speicherbedarf verschiedener Lösungswege vergleichen.
Merge Sort in Python visualisieren
O(n log n)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Beispielcode
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]))Erwartete Ausgabe
[3, 9, 10, 27, 38, 43, 82]So funktioniert es
Das Zusammenführen benötigt lineare Zeit pro Ebene. Insgesamt beträgt die Laufzeit O(n log n), zusätzlich wird O(n) Speicher verwendet.
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungsaufgaben
Verändere Eingaben und Randfälle, bevor du die Lösung mit größeren Datenmengen testest.
- Teste leere Eingaben, ein Element und doppelte Werte.
- Gib den Zustand nach jedem Schritt aus.
- Vergleiche Laufzeit und Speicherbedarf mit einem alternativen Verfahren.