title: Divide and conquer: Merge sort
body: <p>I'm fairly new to Haskell and don't understand the following divide and conquer construct:</p>
  
  <pre><code>{-     trivial        solve       split        combine       input/output-}
  dc :: (a -&gt; Bool) -&gt; (a -&gt; b) -&gt; (a -&gt; [a]) -&gt; ([b] -&gt; b) -&gt; a -&gt; b
  dc trivial solve split combine = x
    where
      x y = if trivial y then solve y
             else (\_ z -&gt; combine z) y (map x (split y))
  </code></pre>
  
  <p>Now I need to implement a merge-sort function based on this construct. I tried to implement some functions but I'm pretty sure that's not how it should work:</p>
  
  <pre><code>trivial :: (Ord a, Num a) =&gt; [a] -&gt; Bool
  trivial [] = True
  trivial (x:[]) = True
  trivial (x:x':xs) = if x&lt;=x' then trivial (x':xs) else False
  
  split :: [a] -&gt; [[a]]
  split (x:[]) = [[x]]
  split (x:xs) = [x] : split xs
  
  combine :: [[a]] -&gt; [a]
  combine [[]] = []
  combine ([]:ys) = combine ys
  combine ((x:xs):ys) = x : combine (xs:ys)
  </code></pre>
  
  <p>So how does the construct above work ? What does "x" and "y" stand for ? What should "trivial" and "solve" (and split/combine) do ?</p>