Mergesort

Kurz: Mergesort teilt die Liste in zwei Hälften, sortiert beide rekursiv und mischt (engl. merge) die sortierten Hälften zu einer sortierten Liste. Es arbeitet in jedem Fall in O(n log n) und ist stabil.

Genauer: Anders als Quicksort hat Mergesort keinen schlechten Sonderfall; dafür braucht es zusätzlichen Speicher von O(n). Es eignet sich gut für verkettete Listen und für das Sortieren von Daten, die nicht in den Arbeitsspeicher passen (externes Sortieren).

Im Detail

def mergesort(liste):
    if len(liste) <= 1:
        return liste
    mitte = len(liste) // 2
    links = mergesort(liste[:mitte])
    rechts = mergesort(liste[mitte:])
    return mische(links, rechts)
 
def mische(a, b):
    ergebnis, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:           # <= erhält die Reihenfolge gleicher Elemente (stabil)
            ergebnis.append(a[i]); i += 1
        else:
            ergebnis.append(b[j]); j += 1
    return ergebnis + a[i:] + b[j:]
 
print(mergesort([38, 27, 43, 3, 9, 82, 10]))   # [3, 9, 10, 27, 38, 43, 82]

Eigenschaften

Merkmal	Wert
Laufzeit (immer)	O(n log n)
Zusatzspeicher	O(n)
Stabil	ja
Paralleliserbar	gut (Hälften unabhängig)

Mergesort ist die Grundlage von TimSort (Python sorted, Java für Objekte). Die Idee „Teile und herrsche“ (Divide and Conquer) findet sich auch bei der binären Suche.

Siehe auch: Quicksort, Bubblesort, Sortieren, Rekursion