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.
Implementing merge sort
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...
- Open src/Main.hs; we will implement merge sort here...