Skip to content

Instantly share code, notes, and snippets.

@kirca
Last active August 29, 2015 14:24
Show Gist options
  • Save kirca/b96862bd92bb8b72bb02 to your computer and use it in GitHub Desktop.
Save kirca/b96862bd92bb8b72bb02 to your computer and use it in GitHub Desktop.
Mergesort in Haskell
mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort (x:[]) = (x:[])
mergeSort xs = merge (mergeSort (fst (halfList xs))) (mergeSort (snd (halfList xs)))
where halfList xs = (take (div len_xs 2) xs, drop (div len_xs 2) xs)
where len_xs = length xs
merge [] [] = []
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
| x < y = x : (merge xs (y:ys))
| otherwise = y : (merge (x:xs) ys)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment