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