Konstruktion eines bitonischen Sortierers

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

2^k-Bitonic-Sort teilt den Input in zwei bitonische Folgen auf und sortiert diese mit jeweils einem 2^{k - 1}-Bitonic-Sort.

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

Sei g(k) die Laufzeit für 2^k-Bitonic-Sort
g(1) = 1
g(k) = 1 + g(k - 1)
$\Rightarrow$ g(k) = k