Skip to content

Instantly share code, notes, and snippets.

@rsslldnphy
Created July 3, 2013 19:03
Show Gist options
  • Save rsslldnphy/5921740 to your computer and use it in GitHub Desktop.
Save rsslldnphy/5921740 to your computer and use it in GitHub Desktop.
Improved merge sort in haskell!
module Main where
import System.Environment
main :: IO ()
main = do
args <- getArgs
mapM_ putStrLn $ sort args
sort :: (Ord a) => [a] -> [a]
sort xs = reduce True $ map (arr) xs
arr :: a -> [a]
arr x = [x]
reduce :: (Ord a) => Bool -> [[a]] -> [a]
reduce _ [] = []
reduce forwards (x:[]) = if forwards then x else reverse x
reduce forwards xs = reduce (not forwards) (combine forwards [] xs)
combine :: (Ord a) => Bool -> [[a]] -> [[a]] -> [[a]]
combine forwards acc [] = acc
combine forwards acc (x:[]) = (reverse x):acc
combine forwards acc (x:y:zs) = let merged = merge forwards x y
acc' = merged:acc
in combine forwards acc' zs
merge :: (Ord a) => Bool -> [a] -> [a] -> [a]
merge forwards xs ys = mergeIter forwards [] xs ys
mergeIter :: (Ord a) => Bool -> [a] -> [a] -> [a] -> [a]
mergeIter _ acc [] [] = acc
mergeIter forwards acc (x:xs) [] = mergeIter forwards (x:acc) xs []
mergeIter forwards acc [] (y:ys) = mergeIter forwards (y:acc) [] ys
mergeIter forwards acc (x:xs) (y:ys)
| x <= y && forwards = mergeIter forwards (x:acc) xs (y:ys)
| x > y && not forwards = mergeIter forwards (x:acc) xs (y:ys)
| otherwise = mergeIter forwards (y:acc) (x:xs) ys
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment