module Data.Tensort.OtherSorts.Mergesort (mergesort) where import Data.Tensort.Utils.ComparisonFunctions (lessThanBit, lessThanRecord) import Data.Tensort.Utils.Types (Record, Sortable (..), Bit) mergesort :: Sortable -> Sortable mergesort :: Sortable -> Sortable mergesort (SortBit [Bit] xs) = [Bit] -> Sortable SortBit ([Bit] -> [Bit] mergesortBits [Bit] xs) mergesort (SortRec [Record] xs) = [Record] -> Sortable SortRec ([Record] -> [Record] mergesortRecs [Record] xs) mergesortBits :: [Bit] -> [Bit] mergesortBits :: [Bit] -> [Bit] mergesortBits = [[Bit]] -> [Bit] mergeAllBits ([[Bit]] -> [Bit]) -> ([Bit] -> [[Bit]]) -> [Bit] -> [Bit] forall b c a. (b -> c) -> (a -> b) -> a -> c . (Bit -> [Bit]) -> [Bit] -> [[Bit]] forall a b. (a -> b) -> [a] -> [b] map (Bit -> [Bit] -> [Bit] forall a. a -> [a] -> [a] : []) where mergeAllBits :: [[Bit]] -> [Bit] mergeAllBits [] = [] mergeAllBits [[Bit] x] = [Bit] x mergeAllBits [[Bit] x, [Bit] y] = [Bit] -> [Bit] -> [Bit] mergeBits [Bit] x [Bit] y mergeAllBits [[Bit]] remaningElements = [[Bit]] -> [Bit] mergeAllBits ([[Bit]] -> [[Bit]] mergePairs [[Bit]] remaningElements) mergePairs :: [[Bit]] -> [[Bit]] mergePairs ([Bit] x : [Bit] y : [[Bit]] remaningElements) = [Bit] -> [Bit] -> [Bit] mergeBits [Bit] x [Bit] y [Bit] -> [[Bit]] -> [[Bit]] forall a. a -> [a] -> [a] : [[Bit]] -> [[Bit]] mergePairs [[Bit]] remaningElements mergePairs [[Bit]] x = [[Bit]] x mergeBits :: [Bit] -> [Bit] -> [Bit] mergeBits :: [Bit] -> [Bit] -> [Bit] mergeBits [] [Bit] y = [Bit] y mergeBits [Bit] x [] = [Bit] x mergeBits (Bit x : [Bit] xs) (Bit y : [Bit] ys) | Bit -> Bit -> Bool lessThanBit Bit x Bit y = Bit x Bit -> [Bit] -> [Bit] forall a. a -> [a] -> [a] : [Bit] -> [Bit] -> [Bit] mergeBits [Bit] xs (Bit y Bit -> [Bit] -> [Bit] forall a. a -> [a] -> [a] : [Bit] ys) | Bool otherwise = Bit y Bit -> [Bit] -> [Bit] forall a. a -> [a] -> [a] : [Bit] -> [Bit] -> [Bit] mergeBits (Bit x Bit -> [Bit] -> [Bit] forall a. a -> [a] -> [a] : [Bit] xs) [Bit] ys mergesortRecs :: [Record] -> [Record] mergesortRecs :: [Record] -> [Record] mergesortRecs = [[Record]] -> [Record] mergeAllRecs ([[Record]] -> [Record]) -> ([Record] -> [[Record]]) -> [Record] -> [Record] forall b c a. (b -> c) -> (a -> b) -> a -> c . (Record -> [Record]) -> [Record] -> [[Record]] forall a b. (a -> b) -> [a] -> [b] map (Record -> [Record] -> [Record] forall a. a -> [a] -> [a] : []) where mergeAllRecs :: [[Record]] -> [Record] mergeAllRecs [] = [] mergeAllRecs [[Record] x] = [Record] x mergeAllRecs [[Record] x, [Record] y] = [Record] -> [Record] -> [Record] mergeRecs [Record] x [Record] y mergeAllRecs [[Record]] remaningElements = [[Record]] -> [Record] mergeAllRecs ([[Record]] -> [[Record]] mergePairs [[Record]] remaningElements) mergePairs :: [[Record]] -> [[Record]] mergePairs ([Record] x : [Record] y : [[Record]] remaningElements) = [Record] -> [Record] -> [Record] mergeRecs [Record] x [Record] y [Record] -> [[Record]] -> [[Record]] forall a. a -> [a] -> [a] : [[Record]] -> [[Record]] mergePairs [[Record]] remaningElements mergePairs [[Record]] x = [[Record]] x mergeRecs :: [Record] -> [Record] -> [Record] mergeRecs :: [Record] -> [Record] -> [Record] mergeRecs [] [Record] y = [Record] y mergeRecs [Record] x [] = [Record] x mergeRecs (Record x : [Record] xs) (Record y : [Record] ys) | Record -> Record -> Bool lessThanRecord Record x Record y = Record x Record -> [Record] -> [Record] forall a. a -> [a] -> [a] : [Record] -> [Record] -> [Record] mergeRecs [Record] xs (Record y Record -> [Record] -> [Record] forall a. a -> [a] -> [a] : [Record] ys) | Bool otherwise = Record y Record -> [Record] -> [Record] forall a. a -> [a] -> [a] : [Record] -> [Record] -> [Record] mergeRecs (Record x Record -> [Record] -> [Record] forall a. a -> [a] -> [a] : [Record] xs) [Record] ys