Recursions and merge sort →
By now, we are all pretty comfortable with recursive functions, using auxiliary functions, etc. Let’s now put these skills to write merge sort algorithm in a recursive fashion. We need the following three ingredients to prepare our recipe
split
function that would take a list and split it into two listsmerge
function that would merge a pair of sorted listsmerge_sort
function that would use the above two to build the sorted list recursively.
Let’s prepare the above one by one. First, the split
function that takes a list lst
as input and splits them and returns a pair of lists as output. The moment we see that we need to return two lists (a pair of lists) as output, intuitively we can imagine that we would need two accumulators, let’s call it a1
and a2
. Next, we will think about the possible cases (patterns).
- The base case is going to be empty list as input in which case our result would be two empty lists (the two accumulators we use).
- If we pass a list that has a single element, one of the lists we return would contain this single element and the other would be an empty list (remember, we need to return two lists as result).
- If there are multiple elements, like any reasonable list, we would pick the first element and push it into the first accumulator, the second element into the second accumulator and then recursively call the auxiliary function on the rest of the list.
So, this is what it looks like - you can match the three items above to the three patterns in the code fragment below - pretty straight forward.
Now, let’s prepare the second item in our list - the merge
function. This is just pattern matching and even simpler than our split
function.
Finally, let’s prepare the merge_sort function that takes a list lst
as input. First we would split the input list into two lists using our split
function. Then, we would recursively call merge_sort
on the two sub-lists (result of split
function) and merge the results of these recursive calls using our merge
function. Again, the base case is the empty list and another possibility is an input list with a single element - both are straight forward.
That was a very intuitive way to write a merge sort algorithm. Hope you all agree with me!