Learn Haskell in minutes(learnxinyminutes.com)

    merge :: Ord x => [x] -> [x] -> [x]
    merge [] y = y
    merge x [] = x
    merge (x:xs) (y:ys) =
      if x < y then
        x:(merge xs (y:ys))
      else
        y:(merge (x:xs) ys)

    odds :: [x] -> [x]
    odds [] = []
    odds (x:xs) = x:(evens xs)

    evens :: [x] -> [x]
    evens = odds . drop 1

    mergesort :: Ord x => [x] -> [x]
    mergesort [] = []
    mergesort [x] = [x]
    mergesort x = merge (mergesort (odds x)) (mergesort (evens x))