8.4 Sortieren im Hypercube

Im Sortiernetzwerk bezieht sich ein Compare-Exchange-Baustein nur auf Linien, deren Kennungen sich um genau ein Bit unterscheiden. Also kann ein Signalverlauf der Länge t durch das Sortiernetzwerk auf dem Hypercube in Zeit O(t) simuliert werden. Folgendes Programm skizziert den Hypercube-Algorithmus; wobei nicht spezifiziert wurde, welcher Prozessor nach einem Datenaustausch jeweils das Maximum und welcher das Minimum behält:

PROCEDURE HC_bitonic_sort(my_id,k)
BEGIN
   FOR i := 0 TO k-1 DO
      FOR j := i DOWNTO 0 DO
         Compare_exchange bzgl. Dimension j
      END
   END
END

Also können n Zahlen auf einem Hypercube mit n Knoten in O($\log^{2}_{}$n) Zeit sortiert werden. Die Kosten betragen O(n · $\log^{2}_{}$n) , also liegt kein kostenoptimaler Algorithmus vor.