Skip to content
Create a gist now

Instantly share code, notes, and snippets.

anonymous /gist:3905696

import qualified Data.List as List
sort cmp lst = mergeMany (map return lst) []
merge (xs@(x:xs')) (ys@(y:ys')) !zs =
case y `cmp` x of
LT -> merge xs ys' (y:zs)
_ -> merge xs' ys (x:zs)
merge xs ys zs = reverseAppend zs $! xs ++ ys
mergeMany [] [] = []
mergeMany [xs] [] = xs
mergeMany [] [ys] = ys
mergeMany (a:b:xss) yss = mergeMany xss $! merge a b [] : yss
mergeMany xss yss = mergeMany (xss ++ yss) []
reverseAppend xs ys = go xs ys
go [] ys = ys
go (x:xs) ys = go xs $! x:ys
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.