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.

 Ancestors (12)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version