素朴なマージソート
code:MSort.hs
msort :: Ord a => a -> a
msort = msortBy compare
msortBy :: (a -> a -> Ordering) -> a -> a
msortBy cmp = mergeAll . sequences
where
sequeces (a:b:xs)
| a cmp b == GT = b, a : sequences xs
| otherwise = a, b : sequences xs
sequences xs = xs
mergeAll x = x
mergeAll xs = mergeAll (mergePairs xs)
mergePairs (a:b:xs) = let !x = merge a b
in x : mergePairs xs
mergePairs xs = xs
merge as@(a:as') bs@(b:bs')
| a cmp b == GT = b:merge as bs'
| otherwise = a:merge as' bs
merge [] bs = bs
merge as [] = as