-- Haskell mergesort
-- This is a true mergesort, though it does not split the same way
-- as in Java

mergesort :: (Ord t) => [t] -> [t]
mergesort [] = []
mergesort [x] = [x]
-- next case implies the first two are not matched,
-- i.e., xs is at least two elements.
-- let creates local variables;
-- (ys, zs) is a tuple.
mergesort xs = let (ys, zs) = splitlist xs
               in merge (mergesort ys) (mergesort zs)

-- merge takes two sorted lists and combines them into a sorted list.
-- run time is Theta(N)

merge :: (Ord t) => [t] -> [t] -> [t]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = 
    if x < y 
    then x : merge xs (y:ys)
    else y : merge (x:xs) ys

-- split a list evenly into two lists,
-- so that each output list contains half of the elements (+ or - 1).
-- Run time is Theta(N).

splitlist :: [t] -> ([t], [t])
splitlist xs = splitloop xs [] []

splitloop [] ys zs = (ys, zs)
splitloop [x] ys zs = (x:ys, zs)
splitloop (x0:x1:xs) ys zs = splitloop xs (x0:ys) (x1:zs)