module Algorithms.DivideAndConquerSpec where

import Algorithms.DivideAndConquer
import           Test.Hspec
import           Test.QuickCheck
import qualified Data.List as List

--------------------------------------------------------------------------------

spec = describe "divide and conquer strategy tests" $ do
         it "mergeSort" $ property $
           \(xs :: [Int]) -> List.sort xs == mergeSort xs


newtype MergeSort a = MergeSort [a]

instance Ord a => Semigroup (MergeSort a) where
  (MergeSort l) <> (MergeSort r) = MergeSort $ merge l r
    where
      merge [] ys = ys
      merge xs [] = xs
      merge a@(x:xs) b@(y:ys) = case x `compare` y of
                              LT -> x : merge xs b
                              EQ -> x : y : merge xs ys
                              GT -> y : merge a ys

instance Ord a => Monoid (MergeSort a) where
  mempty = MergeSort []


mergeSort :: Ord a => [a] -> [a]
mergeSort = (\(MergeSort xs) -> xs) . divideAndConquer (\x -> MergeSort [x])