Okay. Well, we saw how merge-sort is supposed to work, or at least the heart of a merge-sort is supposed to work, and I wanted to show you the actual code for that routine working. Then we'll go on to show how it gets embedded in a bigger routine that can be called on originally, a totally unordered array and produce a sorted array. So first off, let's go and look at our code. I'll forget, one of the reasons we're doing this, and that we're not satisfied with bubble sort is, bubble sort is n squared, and this is order n log n. Again, we have our print array routine, just to see how things work. Here's that merge. Let's look at it individually. Now, in this version, I'm just going to assume that both a and b are the same size, and that c is twice the size of a and b. That will simplify it little bit. The one I showed you on the whiteboard allowed for two different sizes. Now, when we embed this in a bigger program, we're going to make a further simplifying assumption, and we're going to assume that the array to be sorted is a power of two, and that's reasonable. If it's not a power two, we can just have a bunch of empty cells. But a power of two makes it a little easier to both understand and implement. So here are indexes for the three piles. I will be pile a, j will be for pile b, and k will be the index for the merged array, c. Here's exactly what we had before. Don't forget the logical and operator, is a short circuit evaluation operator. In other words, if the first thing is false, the while loop stops. It doesn't have to check that j is less than how many. So we test which is larger in the two piles, and then we increment the merged pile by the element which is smaller. In this case, it was found to be a. So the a and x goes up, and of course, the element in the merge pile goes up. Otherwise, the b pile had the smaller element, and that gets indexed. Again, the merge pile is incremented by one. Then we do the cleanup, means we've gotten through one or the other of the piles, and the remaining elements have to be sorted. So we just decide which of the piles we're finished with, and then put them in the sorted pile. We'll go back to something we're used in merge sort as well. We're going to use a hard-wired size of five. We're going to have two grading scores. Here we see that a and b are already sorted, and c is going to be the merged array. Then we're going to print out the grades in a, and the grades in b, and then show that the merge indeed produces sorted grades. So let's go ahead. I've already compiled this, and let me run it. Sure enough, you can see in the bottom part of the window, that my grades, I branded earlier as well. My grades are 67, 82, 83, 88, 99 in the a's, and the b's 58, 69, 72, 81, 88. So 58 would be compared to 67, 58 would be placed here, 67 would be compared to 69, 67 would be placed here, 69 would be compared to 82, 69 would be placed here, 72 would be compared to 82, 72 would be placed there, 81 would be compared to 82, then 81 would be placed there. Then 88 would be compared to 83, and then 88 with 88, doesn't matter. We get two 88s, and then we do the cleanup 88 and 89, and it works. Okay. Now, we're going to go ahead in the next segment and show how to embed this into a program that starts with an unsorted, completely unsorted array, and that's a assorted array.
