merge_sort.hs

main = putStrLn $ merge_sort "0553241" -- prints 0123455

merge_sort :: (Ord a) => [a] -> [a]
merge_sort []  = []
merge_sort [x] = [x]
merge_sort xs = merge (merge_sort $ evens xs) (merge_sort $ odds xs)
  
merge :: (Ord a) => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge xs@(x:t) ys@(y:u)
  | x <= y    = x : merge t ys
  | otherwise = y : merge xs u

evens :: [a] -> [a]
evens []  = []
evens [x] = [x]
evens (x:_:xs) = x : evens xs

odds :: [a] -> [a]
odds []  = []
odds [x] = []
odds (_:x:xs) = x : odds xs

-- also see https://wiki.haskell.org/Performance/Laziness