Skip to content

Instantly share code, notes, and snippets.

@rdbuf
Created August 27, 2017 20:49
Show Gist options
  • Save rdbuf/066aa34e671217f3b398eb7a78fd6a4f to your computer and use it in GitHub Desktop.
Save rdbuf/066aa34e671217f3b398eb7a78fd6a4f to your computer and use it in GitHub Desktop.
Naive mergesort implementation in Haskell
import Data.List.Utils (merge)
import Data.List.Split (chunksOf)
import Control.Monad (join)
import Control.Arrow -- (***)
import Data.List (sort)
dat = [4,3,2,4,5,6,3,22,4,6,2,1,10,1234,12351,2134,51] :: [Int]
makePair :: [[t]] -> ([t], [t])
makePair (x:y:[]) = (x, y)
msort :: Ord t => [t] -> [t]
msort [single] = [single]
msort multiple = uncurry merge $ join (***) msort $ makePair $ chunksOf (ceiling $ fromIntegral (length multiple) / 2) multiple
main = do
print $ msort dat
print $ sort dat
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment