import ToSort
import ToSortN

merge xs [] = xs
merge [] xs = xs
merge (x : xs) (y : ys)
    | x < y = x : merge xs (y : ys)
    | otherwise = y : merge ys (x : xs)

mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergeSort ys) (mergeSort  zs)
    where (ys,zs) = splitAt (quot (length xs) 2) xs