merge :: [Integer] -> [Integer] -> [Integer]
merge [] lst = lst
merge lst [] = lst
merge (h1:t1) (h2:t2) = if h1 < h2 then
  [h1] ++ merge t1 (h2:t2)
  else
  [h2] ++ merge (h1:t1) t2

sort :: [Integer] -> [Integer]
sort [] = []
sort [x] = [x]
sort lst = let
  mid = div (length lst) 2
  (left, right) = splitAt mid lst
  in merge (sort left) (sort right)

main :: IO ()
main = let
  lst = [10, 42, 2, 23, 666, 1, -94, 52]
  in print $ sort lst