public
anonymous / gist:3905696
Created

  • Download Gist
gistfile1.hs
Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
import qualified Data.List as List
 
sort cmp lst = mergeMany (map return lst) []
where
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
where
go [] ys = ys
go (x:xs) ys = go xs $! x:ys

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.