Merge Sort
Merge Sort gehört zu den schnellsten Sortieralgorithmen. Viele Anwendungen verwenden in der Praxis verschiedene Varianten von Merge Sort. Wir haben bereits Algorithmen kennengelernt, die in einer quadratischen Laufzeit ausgeführt werden, wie zum Beispiel Bubble Sort oder Selection Sort. Merge Sort ist deutlich schneller als alle quadratischen Sortierverfahren und hat eine Laufzeit von .
Merge Sort basiert auf dem Divide-and-Conquer-Prinzip: Er sortiert rekursiv Teilabschnitte des Arrays und führt diese anschließend zusammen. Der Kern des Algorithmus ist das effiziente Zusammenführen zweier bereits sortierter Arrays zu einem einzigen sortierten Array. Während seines Ablaufs teilt Merge Sort das Array in zwei Hälften, sortiert zunächst die erste Hälfte rekursiv, dann die zweite Hälfte rekursiv und fasst schließlich beide sortierten Teilarrays zusammen:
def merge(a, b):
i, j, res = 0, 0, [] # Indizes für a und b sowie das Ergebnisarray
while i < len(a) or j < len(b): # Solange noch Elemente übrig sind
ai = a[i] if i < len(a) else float('inf')
bj = b[j] if j < len(b) else float('inf')
if ai < bj: # Wenn a[i] < b[j], nimm a[i]
res.append(ai) # Füge a[i] zum Ergebnis hinzu
i += 1 # Gehe zum nächsten Element in a
else: # Wenn a[i] >= b[j], nimm b[j]
res.append(bj) # Füge b[j] zum Ergebnis hinzu
j += 1 # Gehe zum nächsten Element in b
return res
def merge_sort(a):
if len(a) <= 1: # Nichts zu sortieren
return a # Gib das Array zurück
l = merge_sort(a[: len(a) // 2]) # Sortiere den linken Teil
r = merge_sort(a[len(a) // 2:]) # Sortiere den rechten Teil
return merge(l, r)In jeder Phase teilt der Algorithmus das Array in zwei Teile, sortiert diese getrennt und führt sie in ein neues, sortiertes Array zusammen. Beachten Sie, dass alle zuvor besprochenen Algorithmen das ursprüngliche Array in place bearbeiten (sie verändern das bestehende Array), während Merge Sort bei jedem Schritt ein neues Array erzeugt. Es ist recht anspruchsvoll, eine In-Place-Variante von Merge Sort zu konstruieren. Können Sie erklären, warum das so schwierig ist?
Werfen wir einen Blick auf ein paar Beispiele, wie Merge Sort Schritt für Schritt an verschiedenen Arrays arbeitet:
[4, 1, -1, 0, 2, 8]
merge_sort([4, 1, -1, 0, 2, 8]):merge_sort([4, 1, -1])merge_sort([0, 2, 8])
merge_sort([4, 1, -1]):merge_sort([4])→ return[4]merge_sort([1, -1])
merge_sort([1, -1]):merge_sort([1])→ return[1]merge_sort([-1])→ return[-1]
- Back to
merge_sort([1, -1])→ return[-1, 1]
- Back to
merge_sort([4, 1, -1])→ return[-1, 1, 4]
merge_sort([0, 2, 8]):merge_sort([0])→ return[0]merge_sort([2, 8])
merge_sort([2, 8]):merge_sort([2])→ return[2]merge_sort([8])→ return[8]
- Back to
merge_sort([2, 8])→ return[2, 8]
- Back to
merge_sort([0, 2, 8])→ return[0, 2, 8]
- Back to
merge_sort([4, 1, -1, 0, 2, 8])→ return[-1, 0, 1, 2, 4, 8]
Challenge
Gegeben ist ein Array bestehend aus
n ganzen Zahlen, das mithilfe des Merge Sort-Algorithmus in absteigender Reihenfolge sortiert werden soll.Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 100 000).Die nächste Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen ( ≤ ≤ ), die das Ausgangsarray darstellen.Ausgabe
Das Programm soll
n durch Leerzeichen getrennte ganze Zahlen in absteigender Reihenfolge ausgeben.Beispiele
Eingabe | Ausgabe |
4
7 4 9 1 | 9 7 4 1 |
5
-4 8 2 -3 6 | 8 6 2 -3 -4 |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 10 MB