= Solution
Apply the supplied bitonic-merging fact directly:
``
merge :: Ord a => [a] -> [a]
merge xs = rounds (levels (length xs)) xs
where
levels n
| n <= 1 = 0
| otherwise = 1 + levels (n `div` 2)
order (x,y)
| x <= y = (x,y)
| otherwise = (y,x)
pass = unpairs . map order . pairs . riffle
rounds 0 ys = ys
rounds r ys = rounds (r-1) (pass ys)
``
For length $n=2^k$, `levels n = k`. Each `pass` performs exactly the required shuffle and adjacent compare-exchange operations. The supplied fact therefore proves that `rounds k` yields ascending order from a <bitonic sequence>. Each pass preserves the <multiset> of entries and costs $\Theta(n)$, giving \b[$\Theta(n\log n)$ time] for $n\ge2$. Length one needs no pass. The definition also harmlessly returns `[]` on empty input.
Back to article page
