Last active
July 10, 2024 00:32
-
-
Save scarf005/dc3e1b5a0c0c46b8c267e35211d8eb6e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| {-# 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)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment