Merge sort.

Merge.hs

module Merge where

sort :: (Ord a) => [a] -> [a]
sort []  = []
sort [x] = [x]
sort xs = merge ls rs
    where
    ls = sort $ take (length xs `div` 2) xs
    rs = sort $ drop (length xs `div` 2) xs

merge :: (Ord a) => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys)
    | x < y     = x : (merge xs (y:ys))
    | otherwise = y : (merge (x:xs) ys)