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.^[1]:800). Er operiert auf zwei sortierten Arrays und und schreibt den sortierten Output in das Array . Die Notation bezeichnet den Teil von von Index bis exklusive .

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 oder (abhängig welches Array mehr Elemente enthält) in 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 zurück, wo wäre, wenn es in eingefügt wäre; dies ist immer eine Zahl zwischen und . 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^[2].

Die Arbeit für das Mischen von zwei Arrays mit insgesamt Elementen beträgt . Dies wäre die Laufzeit für eine sequentielle Ausführung des Algorithmus, welche optimal ist, da mindestens Elemente in das Array 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 , da das größere Array perfekt in zwei Hälften aufgeteilt wird. Werden nun die Kosten für die binäre Suche hinzugefügt, erhalten wir folgende Rekurrenz:

.

Die Lösung ist . Dies ist also die Laufzeit auf einer idealen Maschine mit einer unbeschränkten Anzahl an Prozessoren^[1]:801-802.

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

1. ↑ ^{a b} 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. 
2. ↑ Victor J. Duvanenko: Parallel Merge. In: Dr. Dobb's Journal. 2011.