Merge sort

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


halve :: [a] -> ([a], [a])
halve xs = (take (length xs `div` 2) xs, drop (length xs `div` 2) xs)


msort :: Ord a => [a] -> [a]
msort [] = []
msort [x] = [x]
msort xs = merge (msort y) (msort z)
              where y, z = halve xs

You'll only receive email when @T publishes a new post

More fromĀ @T