mergesort.hs

{-# LANGUAGE OverloadedRecordDot #-}
{-# LANGUAGE DuplicateRecordFields #-}
{-# LANGUAGE NoFieldSelectors #-}

import Data.List (intercalate)

mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs  = merge (mergeSort left) (mergeSort right)
  where (left, right) = splitAt (length xs `div` 2) xs

merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge xs@(x : xs') ys@(y : ys')
  | x <= y    = x : (merge xs' ys)
  | otherwise = y : (merge xs ys')

data Person = Person { group :: String, name :: String }
  deriving (Show, Eq)

instance Ord Person where
  compare a b = compare a.group b.group

main :: IO ()
main = do
  let xs = [4,1,2,6,7,3,8,5,9,10]
  print (mergeSort xs)
  
  -- merge sort is stable
  let ys = [ Person{ group = "nanoha", name = "Fate" }
           , Person{ group = "bebop", name = "Jet" }
           , Person{ group = "2hu", name = "Renk" }
           , Person{ group = "nanoha", name = "Nanoha" }
           , Person{ group = "bebop", name = "Spike" }
           , Person{ group = "2hu", name = "Mary" }
           , Person{ group = "nanoha", name = "Vita" }
           ]
  putStrLn $ intercalate "\n" (map show (mergeSort ys))