Apply the supplied bitonic-merging fact directly:For length ,
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)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 , giving time for . Length one needs no pass. The definition also harmlessly returns [] on empty input. Articles by others on the same topic
There are currently no matching articles.