= Bitonic sorting algorithm
A <divide-and-conquer algorithm> that sorts two halves, reverses one result to form a <bitonic sequence>, then performs a bitonic merge. For the shuffle-and-adjacent-comparison merging network on $n=2^k$ entries, $k$ passes each cost $\Theta(n)$, so merging costs $\Theta(n\log n)$. The complete <recurrence relation> is $T(n)=2T(n/2)+\Theta(n\log n)$, giving $\Theta(n(\log n)^2)$ time. A compare-exchange operation preserves the <multiset> of entries while putting its two selected entries in order.
Back to article page
