8.6 Quicksort im Hypercube

Die rekursive Sortiermethode Quicksort läßt sich als sequentielles Programm wie folgt darstellen:

PROCEDURE quicksort(Menge M)
BEGIN
     waehle Pivotelement x;
     partitioniere M in M₁ und M₂ mit M₁ $\leq$ x < M₂ ;
     quicksort (M₁) ;
     quicksort (M₂)
END

Bei optimaler Wahl des Pivotelements und bei linearem Aufwand zum Partitionieren gilt für die Laufzeit t(n) zum Sortieren von n Zahlen

Würden beide rekursive Aufrufe parallel laufen, beträgt die Laufzeit

Bei n Prozessoren entstehen Kosten O(n ²) . Eine Verbesserung ist nur zu erreichen, wenn die Partitionierung beschleunigt wird.
Folgende Quicksort-Variante verwendet p = 2^k Prozessoren im Hypercube. Zu Beginn hat jeder Prozessor ${\frac{n}{p}}$ Zahlen in seiner lokalen Menge M gespeichert. In jeder Iteration wird in jedem Subwürfel ein Pivotelement zufällig gewählt und durch one-to-all-broadcast im Subwürfel verbreitet.

PROCEDURE HC_quicksort(Menge M)
BEGIN
     sortiere M sequentiell;
     FOR i := 0 TO k-1 DO
         x := Pivotelement;
         partitioniere M in M₁ und M₂ mit M₁ $\leq$ x < M₂ ;
         IF BIT (my-id, i) = 0
         THEN
             verschicke M₂ ueber Dimension i;
             erhalte C ueber Dimension i;
             M := M₁ $\cup$ C durch Mischen
                 ELSE
             erhalte C ueber Dimension i;
             verschicke M₁ ueber Dimension i;
             M := M₂ $\cup$ C durch Mischen
         END
     END
END