Dagens rekursion

merge :: Ord key => [(key, x)] -> [(key, x)] -> [(key, x)]
merge [] ys = ys
merge xs [] = xs
merge xs@((kx, vx):tx) ys@((ky, vy):ty)
  | kx <= ky = (kx, vx) : merge tx ys
  | otherwise = (ky, vy) : merge xs ty

sort :: Ord key => [(key, x)] -> [(key, x)]
sort [] = []
sort [a] = [a]
sort [a, b]
  | fst a <= fst b = [a, b]
  | otherwise = [b, a]
sort list = merge (sort left) (sort right)
  where
    n = length list `div` 2
    left = take n list
    right = drop n list