Created
May 10, 2013 23:10
-
-
Save graue/5558121 to your computer and use it in GitHub Desktop.
Merge sort in Haskell
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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