Implementing merge sort

In this recipe, we will implement merge sort.  The merge sort that we are implementing is bottoms-up merge sort. In bottoms-up merge sort, we start by sorting pairs of elements in the list. Then, gradually, we start merging them in pairs, until we have only one left. 

Getting ready

Use Stack to create a new project, merge-sort, with the simple template and build it, after changing the directory to the project folder:

      > stack new merge-sort simple
      > stack build

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...