Merge-Algorithmen (von englisch merge ‚verschmelzen‘) sind eine Familie von Algorithmen, die mehrere sortierte Listen als Eingabe erhalten und eine einzelne sortierte Liste ausgeben, welche alle Elemente der Eingabelisten enthält. Merge-Algorithmen werden in vielen Algorithmen als Unterprogramm verwendet. Ein bekanntes Beispiel dafür ist Mergesort.

Anwendung

Der Merge-Algorithmus spielt eine wichtige Rolle im Mergesort Algorithmus, einem vergleichsbasierten Sortieralgorithmus. Konzeptionell besteht der Mergesort-Algorithmus aus zwei Schritten:

1. Teile die Eingabe rekursiv in kürzere Listen von ungefähr gleicher Länge, bis jede Liste nur noch ein Element enthält. Eine Liste, welche nur ein Element enthält, ist nach Definition sortiert.
2. Verschmilz wiederholt die kürzeren Listen, bis eine einzelne Liste alle Elemente enthält. Diese Liste ist nun die fertig sortierte Liste.

Der Merge-Algorithmus wird als Teil des Mergesort-Algorithmus immer wieder ausgeführt.

Ein Beispiel für Mergesort wird im Bild dargestellt. Man beginnt mit einer unsortierten Liste aus 7 Zahlen. Das Array wird in 7 Partitionen aufgeteilt, wovon jede nur ein Element enthält. Die sortierten Listen werden dann verschmolzen, um längere sortierte Listen zu liefern, bis nur noch eine sortierte Liste übrig ist.

Verschmelzen von zwei Listen

Das Verschmelzen von zwei sortierten Listen kann in linearer Zeitkomplexität und mit linearem Platz erfolgen. Der folgende Pseudocode zeigt einen Algorithmus, welcher zwei Listen A und B in eine neue Liste C verschmilzt. Die Funktion kopf gibt das erste Element der Liste zurück. Entfernen des ersten Elements wird typischerweise über das Inkrementieren eines Pointers realisiert.

programm merge(A, B)
    eingabe A, B : Liste
    ausgabe Liste

    C := neue leere Liste
    solange A ist nicht leer und B ist nicht leer
        wenn kopf(A) ≤ kopf(B) dann
            hänge kopf(A) an C an
            entferne den Kopf von A
        sonst
            hänge kopf(B) an C an
            entferne den Kopf von B

    // Entweder A oder B ist leer. Nun muss noch die andere Liste an C angehängt werden.
    solange A ist noch nicht leer
        hänge kopf(A) an C an
        entferne den Kopf von A
    solange B ist noch nicht leer
        hänge kopf(B) an C an
        entferne den Kopf von B

    ausgabe C

Das Erstellen einer neuen Liste C kann vermieden werden. Dadurch wird der Algorithmus allerdings langsamer und schwerer zu verstehen.

k-Wege-Mischen

Beim k-Wege-Mischen werden k sortierte Listen zu einer einzelnen, sortierten Liste verschmolzen, welche die gleichen Elemente wie die Ursprungslisten enthält. Sei n die Gesamtzahl der Elemente. Dann ist n die Größe der Ausgabe-Liste und auch die Summe der Größen der Eingabe-Listen. Das Problem kann in einer Laufzeit von O(n log k) und mit einem Platzbedarf von O(n) gelöst werden. Es existieren verschiedene Algorithmen.

programm merge(L1, …, Ln)
  erstelleBaum(kopf von L1, …, Ln)
  solange Baum hat Elemente
    gewinner := baum.gewinner
    ausgabe gewinner.wert
    neu := gewinner.zeiger.nächsterEintrag
    spieleNeu(gewinner, neu) // Replacement selection

programm spieleNeu(knoten, neu)
  verlierer, gewinner := spiele(knoten, neu)
  knoten.wert := verlierer.wert
  knoten.zeiger := verlierer.zeiger
  wenn knoten nicht Wurzel
    spieleNeu(knoten.parent, gewinner)

programm erstelleBaum(elemente)
  nächsteEbene := new Array()
  solange elemente nicht leer
    el1 := elemente.take() // ein Element nehmen
    el2 := elemente.take()
    verlierer, gewinner := spiele(el1, el2)
    parent := new Node(el1, el2, verlierer)
    nächsteEbene.add(parent)
  wenn nächsteEbene.länge == 1
    ausgabe nächsteEbene // nur Wurzel
  sonst
    ausgabe erstelleBaum(nächsteEbene)

{2, 7, 16}
{5, 10, 20}
{3, 6, 21}
{4, 8, 9}

Paralleles Mischen

Eine parallele Version des binären Mischens dient als Baustein für einen parallelen Mergesort Algorithmus. Der folgende Pseudocode demonstriert einen parallelen Teile-und-Herrsche Mischalgorithmus (adaptiert von Cormen et al.^:800). Er operiert auf zwei sortierten Arrays ${\displaystyle A}$ und ${\displaystyle B}$ und schreibt den sortierten Output in das Array ${\displaystyle C}$. Die Notation ${\displaystyle A[i...j]}$ bezeichnet den Teil von ${\displaystyle A}$ von Index ${\displaystyle i}$ bis exklusive ${\displaystyle j}$.

algorithm merge(A[i...j], B[k...ℓ], C[p...q]) is
    inputs A, B, C : array
           i, j, k, ℓ, p, q : indices

    let m = j - i,
        n = ℓ - k

    if m < n then
        swap A and B  // ensure that A is the larger array: i, j still belong to A; k, ℓ to B
        swap m and n

    if m ≤ 0 then
        return  // base case, nothing to merge

    let r = ⌊(i + j)/2⌋
    let s = binary-search(A[r], B[k...ℓ])
    let t = p + (r - i) + (s - k)
    C[t] = A[r]

    in parallel do
        merge(A[i...r], B[k...s], C[p...t])
        merge(A[r+1...j], B[s...ℓ], C[t+1...q])

Der Algorithmus beginnt, indem entweder ${\displaystyle A}$ oder ${\displaystyle B}$ (abhängig welches Array mehr Elemente enthält) in zwei Hälften aufgeteilt wird. Anschließend wird das andere Array in zwei Teile aufgeteilt: Der erste Teil enthält die Werte, die kleiner als der Mittelpunkt des ersten Arrays sind, während der zweite Teil alle Werte beinhaltet, die gleich groß oder größer als der Mittelpunkt sind. Die Unterroutine binary-search gibt den Index in ${\displaystyle B}$ zurück, wo ${\displaystyle A[r]}$ wäre, wenn es in ${\displaystyle B}$ eingefügt wäre; dies ist immer eine Zahl zwischen ${\displaystyle k}$ und ${\displaystyle l}$. Abschließend wird jede Hälfte rekursiv gemischt. Da die rekursiven Aufrufe unabhängig voneinander sind, können diese parallel ausgeführt werden. Ein Hybridansatz, bei dem ein sequentieller Algorithmus für den Rekursionsbasisfall benutzt wird, funktioniert gut in der Praxis.

Die Arbeit für das Mischen von zwei Arrays mit insgesamt ${\displaystyle n}$ Elementen beträgt ${\displaystyle {\mathcal {O}}(n)}$. Dies wäre die Laufzeit für eine sequentielle Ausführung des Algorithmus, welche optimal ist, da mindestens ${\displaystyle n}$ Elemente in das Array ${\displaystyle C}$ kopiert werden. Um den Span des Algorithmus zu berechnen, ist es notwendig, eine Rekurrenzrelation aufzustellen und zu lösen. Da die zwei rekursiven Aufrufe von merge parallelisiert sind, muss nur der teurere der beiden Aufrufe betrachtet werden. Im schlimmsten Fall beträgt die maximale Anzahl an Elementen in einem Aufruf ${\textstyle {\frac {3}{4}}n}$, da das größere Array perfekt in zwei Hälften aufgeteilt wird. Werden nun die ${\displaystyle \Theta \left(\log(n)\right)}$ Kosten für die binäre Suche hinzugefügt, erhalten wir folgende Rekurrenz:

${\displaystyle T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{merge}}\left({\frac {3}{4}}n\right)+\Theta \left(\log(n)\right)}$.

Die Lösung ist ${\displaystyle T_{\infty }^{\text{merge}}(n)=\Theta \left(\log(n)^{2}\right)}$. Dies ist also die Laufzeit auf einer idealen Maschine mit einer unbeschränkten Anzahl an Prozessoren^:801-802.

Achtung: Diese parallele Mischroutine ist nicht stabil. Wenn gleiche Elemente beim Aufteilen von ${\displaystyle A}$ und ${\displaystyle B}$ separiert werden, verschränken sie sich in ${\displaystyle C}$, außerdem wird das Tauschen von ${\displaystyle A}$ und ${\displaystyle B}$ die Ordnung zerstören, falls gleiche Items über beide Inputarrays verteilt sind.

Einzelnachweise

1. ↑ Steven Skiena: The Algorithm Design Manual. 2nd Auflage. Springer Science+Business Media, 2010, ISBN 1-84996-720-2, S. 123. 
2. ↑ Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola: Practical in-place mergesort. In: Nordic J. Computing. 3. Jahrgang, Nr. 1, 1996, S. 27–40. 
3. ↑ Jon Louis Bentley: Programming Pearls. 2nd Auflage. Addison-Wesley, 2000, ISBN 0-201-65788-0, S. 147–162. 
4. 1 2 Donald Knuth: Sorting and Searching (= The Art of Computer Programming. Band 3). 2nd Auflage. Addison-Wesley, 1998, ISBN 0-201-89685-0, Chapter 5.4.1. Multiway Merging and Replacement Selection, S. 252–255. 
5. 1 2 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford: Introduction to algorithms. Third edition Auflage. MIT Press, Cambridge, Mass. 2009, ISBN 978-0-262-27083-0. 
6. ↑ Victor J. Duvanenko: Parallel Merge. In: Dr. Dobb's Journal. 2011. 

Siehe auch

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Seiten 158–160 con Abschnitt 5.2.4: Sorting by Merging. Abschnitt 5.3.2: Minimum-Comparison Merging, Seiten 197–207.
• Mergesort