So now we're going to show you the whole ball of wax for Merge Sort. This is going to be somewhat specialized because I'm only going to allow it on powers of two because that's simplifies recording some. You might like to look into how to modify this so that it could work on an arbitrary sized data set. So some of this is going to be familiar. Here's our print array as before, and here's that internal sort routine. Now, I won't go back over that. Now, here's where it gets you, so let's look at this. We have a set of keys, sometimes we call that data, but the reason we're calling that a key is that's technical. The key means the item that's being sorted on. Later in our next course when we talk about things like structs where multiple pieces of information are put together, so you can imagine that you're in a payroll database for your company, and you might be sorted according to an employee number, which might indeed be your social security number. So within that company and that database, if they had sorted data, it would be based on some key and that would make it efficient to go look up all sorts of information about you. So again, this is going to be a power of two. How many will be power of two? So that's going to be 2, 4, 8, 16, 32 etc. So inside the routine, there's going to be two indexes. The indexes are going to keep track of the powers of two, and it's generally going to sort at first two elements, and then four elements, and then eight elements until it's all done. So the index k is being ramped up by powers of two. K equals 1 until k is less than how many, and we multiply k by a power of two. So it'll start at one. That means two elements will be compared and only two elements and those will be that in order and then we can go to four elements, and then eight elements until we finish the whole array of keys. Then internally, we had do the comparisons. So here's where the actual merges occurring of the small sets, and I'm using address arithmetic. So this, for example, is saying for the key offset by the index j, which initially is zero, look at the key offset by the index zero plus one. So it's really comparing those two elements, and is saying, place some n in array where they're being merged and that's w. So it'll be placed in w starting at w of zero. How many keys will be looked at? In this case, is going to be one in each element. So what you're going to find is one element is compared to one element then placed into w. Then that gets repeated over and over again, and then the keys are updated. So everything is being sorted in powers of two until we're all done. Here let's go and look at our key array, which will be a, and again it looks like our old grades are a. Grade some more unsorted elements, there are eight of them, so it is a power of two. We're going to print my grades and then we're going to do the full merge sort, and we're going to show that in a at the end of this will be the sorted grades, and there we are. So what was happening internally is, we started with this unordered array and then we passed it into merge sort which had essential routine, the merge routine. What was really happening was 99, 82 were being compared and they were putting in order, and then we would jump the index to 74 and 85, and they would be input in order. Then 92 and 67 were being put in order, and then 76 and 49 were being put in order. So after in effect, the first pass through the outer loop, all of these pairs were in order. You can imagine after they were in order, and then I'll let you work this out on your own, or you can try that trick I showed earlier of putting in a print array showing how each iteration works. That indeed is what we did in book on C if you look in section 6.9 where this algorithm is described in more detail. We then have pairs that are in order and next through the loop, we're taking the 82, 99, 74, 85, and merging them. Similarly, merging the 67, 92 with the 49, 76, and then all four of these elements would be done. Then we up say amount of what we're looking at by a factor of two. So we first look at one element, then two elements, then four elements. Four elements to be done because we only have eight elements. But we keep going even if we had a million elements by doubling the size until we reach that number of elements that would be fully sorted. Again, it's a divide-and-conquer strategy and it ends up being quartered nlogn.
