User:ParAlgMergeSort/sandbox/Parallel merge sort deutsch
Paralleler Mergesort
[edit]Mergesort lässt sich aufgrund des divide-and-conquer Ansatzes gut parallelisieren. Verschiedene parallele Varianten wurden in der Vergangenheit enwickelt. Manche sind stark verwandt mit der hier vorgestellten sequentiellen Variante, während andere eine grundlegend verschiedene Struktur besitzen und das K-Wege-Mischen verwenden.
Mergesort mit parallelen Rekursionsaufrufen
[edit]Der sequentielle Mergesort kann in zwei Phasen erklärt werden, die Teile-phase und anschließend die Mischphase. Die erste besteht aus vielen rekursiven Aufrufen, in denen alle Teilungsprozesse aufrufen bis die Teilsequenzen trivial sortiert sind (das heißt nur ein oder kein Element enthalten). Ein intuitiver Ansatz wäre es, diese rekursiven Aufrufe zu parallelisieren. Der folgende Pseudocode beschreibt den klassischen Mergesort Algorithmus mit paralleler Ausführung der Rekursion indem die fork-and-join Schlüsselwörter verwendet werden.
Dieser Algorithmus ist die triviale Modifikation des sequentiellen Algorithmus und ist noch nicht optimal. Sein Speedup ist dementsprechend auch nicht beeindruckend. Er hat einen Spann von , was nur eine Verbesserung um den Faktor ist im Vergleich zur sequentiellen Version (siehe auch Introduction to Algorithms). Dies liegt hauptsächlich an der sequentiellen Mischmethode, welche der Flaschenhals in der parallelen Ausführung ist.
