= 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)=2T(n/2)+\Theta(n\log n)$, so summing the levels gives \b[$\Theta(n(\log n)^2)$ time]. Equal keys cause no difficulty; ascending and descending here permit equality. This is a <bitonic sorting algorithm>.
Back to article page
