Skip to content

Instantly share code, notes, and snippets.

@deque-blog

deque-blog/merge_sort_with_fold.hs

Last active December 25, 2016 09:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save deque-blog/78052503b7516c30e7df9c20e53d2662 to your computer and use it in GitHub Desktop.
Save deque-blog/78052503b7516c30e7df9c20e53d2662 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
merge_sort_with_fold.hs
foldMergeSort :: (Ord a) => [a] -> [a]
foldMergeSort =
foldl1 (flip merge) . map snd . foldl addToCounter []
where
addToCounter counter x = propagate ((1::Int,[x]) : counter)
propagate [] = []
propagate [x] = [x]
propagate counter@(x:y:xs) -- x arrived last => combine on right
| fst x == fst y = propagate ((fst x + fst y, merge (snd y) (snd x)) : xs)
| otherwise = counter
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment