 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.