Skip to content

Instantly share code, notes, and snippets.

@graue
Created May 10, 2013 23:10
Show Gist options
  • Save graue/5558121 to your computer and use it in GitHub Desktop.
Save graue/5558121 to your computer and use it in GitHub Desktop.
Merge sort in Haskell
mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = combineSortedLists
(mergeSort firstHalf)
(mergeSort secondHalf)
where (firstHalf, secondHalf) = splitInHalf xs
splitInHalf :: [a] -> ([a], [a])
splitInHalf xs = splitAt halfLength xs
where halfLength = (length xs) `div` 2
combineSortedLists :: Ord a => [a] -> [a] -> [a]
combineSortedLists = combineSortedLists_ []
-- Combine two lists with an accumulator in front, for tail-recursion.
combineSortedLists_ :: Ord a => [a] -> [a] -> [a] -> [a]
combineSortedLists_ acc [] ys = (reverse acc)++ys
combineSortedLists_ acc xs [] = (reverse acc)++xs
combineSortedLists_ acc (x:xs) (y:ys)
| y < x = combineSortedLists_ (y:acc) (x:xs) ys
| otherwise = combineSortedLists_ (x:acc) xs (y:ys)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment