How to do it...

1. Open src/Main.hs; we will implement merge sort here.
2. We will start with the implementation of two utility functions; group2 and merge.
3. The group2 function is used to divide the input list in pairs. We will ensure that the pairs are sorted in the result. A single element is considered sorted:

        -- Group elements in groups of twos, but when we group it we 
        keep
        them
        -- sorted. 
        group2 :: Ord a => [a] -> [[a]]
        group2 [] = []
        -- A single element is already sorted.
        group2 (x:[]) = [[x]]
        -- Create groups of two and sort them
        group2 (x:y:xs) = (sortPair x y) : group2 xs
        where
         sortPair x y | x >= y    = y : x : []
                 | otherwise = x : y : []

4. The merge function is used to merge two input lists. It is assumed that the input lists are already sorted. While merging, we look at the elements of two input lists one by one, and put them in correct order.

        -- Assume that two lists are sorted, and merge them in the 
        increasing
        -- order. 
        merge :: Ord a => [a] -> [a] -> [a]
        merge [] ys = ys  -- If one of the input is empty, the other 
        list is the result. 
        merge xs [] = xs
        merge (x:xs) (y:ys)  -- Compare heads of inputs while merging. 
        Continue recursively
        | x >= y    = y : merge (x:xs) ys
        | otherwise = x : merge xs (y:ys)

5. We will continue merging until we have only one list left. We will use the worker pattern for recursion. We will implement an internal function mergeStep' to merge adjacent lists:

        mergeSort :: Ord a => [a] -> [a]
        mergeSort xs = mergeSort' (group2 xs)
        where
          mergeSort' :: Ord a => [[a]] -> [a]
          mergeSort' [] = []
          mergeSort' (xs:[]) = xs
          mergeSort' xss = mergeSort' (mergeStep' xss)
    
          mergeStep' :: Ord a => [[a]] -> [[a]]
          mergeStep' [] = []
          mergeStep' (xs:[]) = [xs]
          mergeStep' (xs:ys:xss) = (merge xs ys) : mergeStep' xss

6. Test the implementation:

        main :: IO ()
        main = do
        let input = [5,2,3,1,7,9,8,4,6,0]
        sorted = mergeSort input
        putStrLn $ "input: " ++ (show input)
        putStrLn $ "sorted: " ++ (show sorted)

7. Run the program, and check the output: