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