Informatik

Wie funktioniert Mergesort?

Mergesort ist ein Divide-&-Conquer-Sortierverfahren: Das Array wird rekursiv in Hälften geteilt, die Hälften werden sortiert und dann paarweise durch ein stabiles Merge-Verfahren zu einer sortierten Gesamtfolge zusammengeführt.

Algorithmus

• Divide: Rekursiv in Hälften bis zu Segmenten der Länge $1$.
• Conquer: Sortiere jede Hälfte rekursiv.
• Merge: Führe die beiden sortierten Teilarrays zu einem sortierten Array zusammen.

Pseudocode

mergesort(array):
    wenn Länge(array) <= 1:
        return array

    mitte = Länge(array) // 2
    links = mergesort(array[0:mitte])
    rechts = mergesort(array[mitte:Länge(array)])

    return merge(links, rechts)

merge(links, rechts):
    sorted_array = []
    solange links und rechts nicht leer:
        wenn links[0] < rechts[0]:
            sorted_array.append(links[0])
            links.remove(links[0])
        sonst:
            sorted_array.append(rechts[0])
            rechts.remove(rechts[0])

    return sorted_array + links + rechts

Beispiel

Start

Teile: in [4,2] und [3,1]

Teile weiter: [4], [2], [3], [1]

Merge der Paare: [2,4] und [1,3]

Finales Merge: [1,2,3,4]