Recently, I was reviewing CS Fundamentals for an upcoming technical interview and was trying to spot the main differences amongst the various comparison sorts. As a teacher, I always taught my students that the best way to learn something is to write about it with the intention of being able to teach someone else. It also helps to find how something is different from another thing to help solidify your knowledge.
Divide with Recursion
Mergesort works through divide and conquer, in that we take an array and divide it in half and continuously divide it until we have n sublists. An array that looks like this:
[6, 1, 12, 2, 45, 7]
would look like this using a recursive approach:
[, , , , , ]
The reason for doing this is because it allows us to assume that each list is sorted, even though it has only one element in it.
I might have jumped a step in not clarifying that the recursive pattern would split the array first like this:
- [6, 1, 12] [2, 45, 7]
- [6, 1] [2, 45] 
Recursion would sort [6, 1] -> [1,6]
Once all the elements are split into n sublists (our base case would be that the length of the subList is < 2), we would merge the sublists.
Using recursion is a difficult concept to understand. I know that when I first started it, I broke my browser with an infinite loop many times. But to start, we have a good base case here which is
Does the subarray have only 1 element in it?
Let’s start with some general concepts:
- Loop over the input array
- Find the middle
- Split the array into sublists until we reach the end
- Compare values
- Merge sorted values until no more sublists remain
So a general pattern of approach can be
// iterate over the input array
// is the beginning value of the array less than the end?
// if yes? Divide the array in half into subarrays
// does the subarray have only 1 element in it?
// if yes? keep dividing
// compare the values and swap positions
// if no? stop dividing and compare the values
// if no? swap the positions of the beginning and end of the input array
// is the length of the array less than or equal to 1? (our base case)
// if yes? return the array
// if no? call the function recursively
The merging is what is accomplished recursively. When I refer to “swap positions”, I am referring to sorting.