Skip to content

Instantly share code, notes, and snippets.

Created December 18, 2011 21:54
Show Gist options
  • Save anonymous/1494599 to your computer and use it in GitHub Desktop.
Save anonymous/1494599 to your computer and use it in GitHub Desktop.
Haskell MergeSort Implementation
import qualified Data.List as L
testList = [5,3,1,1,2,-1,0,33,10]
main = print $ mergeSort testList `isSameAs` L.sort testList
isSameAs = (==)
mergeSort :: (Ord a) => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge left right
where
left = mergeSort $ take (length xs `div` 2) xs
right = mergeSort $ drop (length xs `div` 2) xs
merge :: (Ord a) => [a] -> [a] -> [a]
merge [] [] = []
merge [] xs | not $ null xs = xs
merge xs [] | not $ null xs = xs
merge (l:lxs) (r:rxs) =
if (l < r)
then (l : merge lxs (r:rxs))
else (r : merge (l:lxs) rxs)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment