Konstruktion eines Sortierers mit Hilfe von Bitonic-Sort

Input: beliebige Folge der Länge 2^k
Output: sortierte Folge der Länge 2^k

2^k-Sort sortiert beide Input-Hälften gegenläufig jeweils mit einem 2^{k - 1}-Sort und schickt das Ergebnis (welches bitonisch ist) in einen 2^k-Bitonic-Sort.

Rekursive Darstellung eines 2^k-Sort $\uparrow$

Sei h(n) die Laufzeit für 2^k-Sort
h(1) = 1
h(k) = h(k - 1) + g(k)
$\Rightarrow$ h(k) = k · (k + 1)/2
$\Rightarrow$ Laufzeit für 2^k Zahlen = O(k ²)
Laufzeit für n Zahlen = O($\log^{2}_{}$n)

Explizite Darstellung eines 2³-Sort $\uparrow$ und seiner Bestandteile