 Solution

ID: 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/f/solution

Sort the two halves ascending, reverse the second, and concatenate to form a bitonic sequence:

sort :: Ord a => [a] -> [a]
sort []  = []
sort [x] = [x]
sort xs  = merge (sort as ++ reverse (sort bs))
  where (as,bs) = halve xs

For a power-of-two length greater than one, both halves are smaller powers of two. By induction, the recursive calls return ascending permutations of their respective inputs. Reversal makes the second half descending, so part (e)'s precondition holds and merge sorts their concatenation without losing entries. This proves both sortedness and sorting permutation preservation. Its recurrence relation is

T (n) = 2 T (n /2) + Θ (n lo g n)

, so summing the levels gives $Θ (n (lo g n)^{2})$ time. Equal keys cause no difficulty; ascending and descending here permit equality. This is a bitonic sorting algorithm.

 New to topics? Read the docs here!