Last time, we learned how we can use recursion to implement binary search. This time we're going to return to sorting and learn about an algorithm called merge sort that uses recursion to help us get better than order and squared complexity. There is a reading associated with merge sort in the lecture materials for this lecture. Here's our problem. We want to sort an array of values in ascending or descending order. One solution is to use merge sort and merge sort uses recursion. That's why we needed to learn about recursion before we could learn about merge sort. Let's now go learn about merge sort and analyze the complexity of that algorithm. For our merge sort example, we're going to sort the same eight element array that we sorted when we were doing those iterative sorting algorithms. I have three function prototypes that we're going to use to support our merge sorting. I have the mergeSort function. In the mergeSort function, I pass in the array that I want to sort and how big that array is. I have the merge function that takes a left side array and how many elements are in that array, a right-side array and how many elements are in that array and merges them together and puts them into this array. We'll take a look at how that works. I have this helper function called copyRange that just copies from this array into this array from start to end. Those are just indexes from array. Let's take a look at merge sort first. As we know, with recursion, we need a termination condition and our termination condition for merge sorting is that the size of the array that we're trying to sort is one. Because we know that an array of a single element is by definition sorted, that means we can stop at this point. We don't have to continue if the array that got passed into merge-sort is only one element big. If it's not one element big, we need to sort both the left and the right-hand sides of the array that got passed in. To do that, we calculate the middle location. For our solution here, we're not just passing a single array through all the recursions like we did with binary search. We don't need a lower bound and an upper bound and adding to the lower bound or any of that stuff. The middle location for the array that got passed in is just count over two. Here's where I use pointers to allocate that array at run-time. Then, I copy from the array that got passed in from zero up to middle location minus one into this left-hand array that I just created. Now, I'm going to calculate the size of the right-hand side of the array. I calculate that as count, how big is the array, minus middle location and you can convince yourself that that's the correct math but trust me it is. Then we create another array for the right-hand side that needs to get sorted. We copy from our original array and to the right hand side starting at middleLocation and going up to count minus one. At this point, our left array has the left half of this original array and our right array has the right half of that original array. Now, we recursively sort both sides. So we merge sort at the left side and we merge sort the right side and that's great. So this is the recursion part. We're going to sort both of those sides making the arrays we're sorting smaller and smaller until we reach the termination condition. Now, because we are splitting in half, this is still order log n doing all the recursive calls. We're going to have log n times some constant recursive calls to sort both sides. Even though on binary search, we picked one side and only recursed down that side as we were trying to find the value we were searching for, this time we're recursing on both sides every time but it's still a log n deep tree because we're splitting in half every time. We have order log n recursions. We're not done yet. That doesn't make this a log n algorithm. That would be awesome but it's not. But we do know at least one piece of our algorithmic complexity. We know we have log n recursions. After we've sorted both the left and the right sides of the array that got passed in, the next thing we do is we merge the left and right sides together into that original array. After we're done merging, we'll be back to this array holding everything that was in the left and the right, but it will be sorted. Let's go see how merge works. Remember we pass in the left side and how many elements are in it. We pass in the right side and how many elements are in it. This is the array that we're going to put those values into once they're merged. The metaphor that I used in the reading for merging is: Think of having too small decks of cards that are approximately the same number of cart and they're face up. Now, you look at those two decks and you pick the smallest card that you see on the top of those two decks and you move it to a new deck. Now, you look at the top cards on the left and right decks and pick the smallest card and move it to a new deck. You just keep doing that until one of the decks is empty. That's what this while loop right here does. While left index is less than left count and right index is less than right count, we're going to keep looping and we pick if the left pile has a card that's less than or equal to the right pile, then we set the next place in the array we're copying into to that left value, and then we bump left index alone. So we haven't actually removed that element from the left-hand array but we've changed where we've said the top of that left a deck of cards is so we know what to compare to the right deck of cards on the next iteration of this while loop. Then, of course, if that's not the case, we moved the right one over and then we bump result index. This is where we are in the array we're copying into because, of course, we need to move that index along as we go as well. So this while loop runs putting the smallest one each time into the new array until one of those decks is empty. Now, you could do "if" statements here to try to figure out which deck is empty and then copy the other one over, but we don't have to because we know while loops can execute zero or more times. So let's say the right deck is empty and the left deck still has some cards in it. We just copy each of the cards from the left deck one by one into that final array that we've been copying into. Here's where the metaphor breaks down a little bit. I know if we actually had a deck, we would just slide it underneath the other one because we know the left deck is already sorted, but because this is a computer, we're moving them one at a time. Now, we get to this while loop but we already know that the right deck was empty in the example we're discussing. So right index is not less than right count. It's in fact equal to right count. So we don't do any of this stuff and that's fine because there's nothing there to copy. The next question is, what is the algorithmic complexity of merge? Because we need to do this in the worst-case, let's talk about the very last merge we do right before we've got the complete array sorted. In that case, the left-hand array has n over two elements. The right-hand array has n over two elements. This array has n elements and we can tell if we had perfect left and right decks and we were moving one from the left, one from the right, one from the left, one from the right, and so on. You can see that this while loop will execute n minus one times as we exhaust one deck and have one card left in the deck and then one of these while loops executes once to grab that last card. That means that we do n of these comparisons n copies over which makes merge order n. How does that help us get to our final algorithmic complexity for merge sort? We need to go back to the mergeSort function. We've already discussed the fact that we have order log n recursions. This merge that we have inside each and every recursion, you can think of it at least conceptually as a nested loop. If we didn't do recursions for the merge sort part, then you could think of those as an outer loop and merges in the inner loop. Even though we have partial recursions and partial iteration here, we still need to multiply the algorithmic complexity of the merge by how many times we're going to do it, right? The kind of how many times would the outer loop execute? We know we're going to do this order log n times because we do it on every recursion so that multiplication gives us n log n which means this is a log linear algorithm order n log n. If you look at the image I gave you of different complexities early on when we started talking about algorithmic complexity, you can see that order n log n is much better than order n squared and the best that we could do with the three sorting algorithms we looked at using iteration was order n squared and this is order n log n. That's how we implement merge sort using recursion. We can also see that merge sort has a much better algorithmic complexity than any of the sorting algorithms we've looked at so far. To recap, in this lecture, we learned how merge sort works and we learned a little more about how recursion works as we explored merge sort. We finally got to a sorting algorithm that's order n log n rather than order n squared.
