Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 4 / e

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