anonymous / gist:3905696
Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist
View gist:3905696
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
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.