[Section 3 - More Comfortable] [Rob Bowden - Harvard University] 

[This is CS50. - CS50.TV] 

So the first question is strangely worded. GDB lets you "debug" a program, but, more specifically, what does it let you do? I'll answer that one, and I don't know what's exactly expected, so I'm guessing it's something along the lines of it lets you step by step walk through the program, interact with it, change variables, do all these things-- basically completely control execution of a program and inspect any given part of the execution of the program. So those features let you debug things. Okay. Why does binary search require that an array be sorted? Who wants to answer that? [student] Because it doesn't work if it's not sorted. >>Yeah. [laughter] If it's not sorted, then it's impossible to split it in half and know that everything to the left is less and everything to the right is greater than the middle value. So it needs to be sorted. Okay. Why is bubble sort in O of n squared? Does anyone first want to give a very quick high-level overview of what bubble sort is? [student] You basically go through each element and you check the first few elements. If they're out of where you swap them, then you check the next few elements and so on. When you reach the end, then you know that the largest element is placed at the end, so you ignore that one then you keep on going through, and each time you have to check one less element until you make no changes. >>Yeah. It's called bubble sort because if you flip the array on its side so it's up and down, vertical, then the large values will sink to the bottom and the small values will bubble up to the top. That's how it got its name. And yeah, you just go through. You keep going through the array, swapping the larger value to get the largest values to the bottom. 

Why is it O of n squared? First, does anyone want to say why it's O of n squared? [student] Because for each run it goes n times. You can only be sure that you've taken the biggest element all the way down, then you have to repeat that for as many elements. >>Yeah. So keep in mind what big O means and what big Omega means. The big O is like the upper bound on how slow it can actually run. So by saying it's O of n squared, it is not O of n or else it would be able to run in linear time, but it is O of n cubed because it is bounded by O of n cubed. If it's bounded by O of n squared, then it's bounded also by n cubed. So it is n squared, and in the absolute worst case it can't do better than n squared, which is why it's O of n squared. So to see slight math at how it comes out to be n squared, if we have five things in our list, the first time how many swaps could we potentially need to make in order to get this? Let's actually just-- How many swaps are we going to have to make in the first run of bubble sort through the array? [student] n - 1. >>Yeah. 

If there are 5 elements, we're going to need to make n - 1. Then on the second one how many swaps are we going to have to make? [student] n - 2. >>Yeah. And the third is going to be n - 3, and then for convenience I will write the last two as then we're going to need to make 2 swaps and 1 swap. I guess the last one may or may not actually need to happen. Is it a swap? I don't know. So these are the total amounts of swaps or at least comparisons you have to make. Even if you don't swap, you still need to compare the values. So there are n - 1 comparisons in the first run through the array. If you rearrange these things, let's actually make it six things so things stack up nicely, and then I'll do 3, 2, 1. So just rearranging these sums, we want to see how many comparisons we make in the entire algorithm. So if we bring these guys down here, then we're still just summing however many comparisons there were. But if we sum these and we sum these and we sum these, it's still the same problem. We just sum those particular groups. 

So now we're summing 3 n's. It's not just 3 n's. It's always going to be n/2 n's. So here we happen to have 6. If we had 10 things, then we could do this grouping for 5 different pairs of things and end up with n + n + n + n + n. So you're always going to get n/2 n's, and so this we'll jot it out to n squared/2. And so even though it's the factor of half, which happens to come in because of the fact that through each iteration over the array we compare 1 less so that's how we get the over 2, but it is still n squared. We don't care about the constant factor of a half. So a lot of big O stuff like this relies on just kind of doing this sort of math, doing arithmetic sums and geometric series stuff, but most of them in this course are pretty straightforward. Okay. Why is insertion sort in Omega of n? What does omega mean? [two students speaking at once - unintelligible]  >>Yeah. Omega you can think of as the lower bound. 

So no matter how efficient your insertion sort algorithm is, regardless of the list that's passed in, it always has to compare at least n things or it has to iterate over n things. Why is that? [student] Because if the list is already sorted, then through the first iteration you can only guarantee that the very first element is the least, and the second iteration you can only guarantee the first two are because you don't know that the rest of the list is sorted. >>Yeah. If you pass in a completely sorted list, at the very least you have to go over all the elements to see that nothing needs to be moved around. So passing over the list and saying oh, this is already sorted, it's impossible for you to know it's sorted until you check each element to see that they are in sorted order. So the lower bound on insertion sort is Omega of n. What's the worst case running time of merge sort, worst case being big O again? So in the worst case scenario, how does merge sort run? [student] N log n. >>Yeah. The fastest general sorting algorithms are n log n. You can't do better. 

There are special cases, and if we have time today--but we probably won't-- we could see one that does better than n log n. But in the general case, you cannot do better than n log n. And merge sort happens to be the one you should know for this course that is n log n. And so we'll actually be implementing that today. And finally, in no more than three sentences, how does selection sort work? Does someone want to answer, and I'll count your sentences because if you go over 3-- Does anyone remember selection sort? Selection sort is usually pretty easy to remember just from the name. You just iterate over the array, find whatever the largest value is or smallest-- whatever order you're sorting in. So let's say we're sorting from smallest to greatest. You iterate over the array, looking for whatever the minimum element is, select it, and then just swap it whatever is in the first place. And then on the second pass over the array, look for the minimum element again, select it, and then swap it with what's in the second position. So we are just picking and choosing the minimum values and inserting them into the front of the array until it is sorted. Questions on that? 

These inevitably appear in the forms you have to fill out when you're submitting the pset. Those are basically the answers to those. Okay, so now coding problems. I already sent out over email-- Did anyone not get that email? Okay. I already sent out over email the space that we're going to be using, and if you click on my name--so I think I'm going to be at the bottom because of the backwards r--but if you click on my name you'll see 2 revisions. Revision 1 is going to be I already copied and pasted the code into Spaces for the search thing you're going to have to implement. And Revision 2 will be the sort thing that we implement after that. So you can click on my Revision 1 and work from there. And now we want to implement binary search. 

Does anyone want to just give a pseudocode high-level explanation of what we're going to have to do for search? Yeah. [student] You just take the middle of the array and see if what you're looking for is less than that or more than that. And if it's less, you go to the half that's less, and if it's more, you go to the half that's more and you repeat that until you just get one thing. [Bowden] Yeah. Notice that our numbers array is already sorted, and so that means that we can take advantage of that and we could first check, okay, I'm looking for the number 50. So I can go into the middle. Middle is hard to define when it's an even number of things, but let's just say we'll always truncate to the middle. So here we have 8 things, so the middle would be 16. I'm looking for 50, so 50 is greater than 16. So now I can basically treat my array as these elements. I can throw away everything from 16 over. Now my array is just these 4 elements, and I repeat. So then I want to find the middle again, which is going to be 42. 42 is less than 50, so I can throw away these two elements. This is my remaining array. I'm going to find the middle again. I guess 50 was a bad example because I was always throwing away things to the left, but by the same measure, if I'm looking for something and it's less than the element I'm currently looking at, then I'm going to throw away everything to the right. So now we need to implement that. Notice that we need to pass in size. We can also not need to hard-code size. So if we get rid of that #define-- Okay. How can I nicely figure out what the size of the numbers array currently is? 

How many elements are in the numbers array? [student] Numbers, brackets, .length? [Bowden] That doesn't exist in C. Need .length. Arrays don't have properties, so there is no length property of arrays that will just give you however long it happens to be. [student] See how much memory it has and divide by how much-- >>Yeah. So how can we see how much memory it has? >>[student] Sizeof. >>Yeah, sizeof. Sizeof is the operator that's going to return the size of the numbers array. And that's going to be however many integers there are times the size of an integer since that's how much memory it's actually taking up. So if I want the number of things in the array, then I'm going to want to divide by the size of an integer. Okay. So that lets me pass in size here. Why do I need to pass in size at all? Why can't I just do up here int size = sizeof(haystack) / sizeof(int)? Why does this not work? [student] It's not a global variable. [Bowden] Haystack exists and we're passing in numbers as haystack, and this is kind of a foreshadowing of what's to come. Yeah. [student] Haystack is just the reference to it, so it would return how big that reference is. Yeah. I doubt in lecture that you've seen the stack yet really, right? We've just spoken about it. So the stack is where all of your variables are going to be stored. 

Any memory that's allocated for local variables is going in the stack, and each function gets its own space on the stack, its own stack frame is what it's called. So main has its stack frame, and inside of it is going to exist this numbers array, and it's going to be of size sizeof(numbers). It's going to have size of numbers divided by size of elements, but that all lives within main's stack frame. When we call search, search gets its own stack frame, its own space to store all of its local variables. But these arguments--so haystack isn't a copy of this entire array. We don't pass in the entire array as a copy into search. It just passes a reference to that array. So search can access these numbers through this reference. It's still accessing the things that live inside of main's stack frame, but basically, when we get to pointers, which should be soon, this is what pointers are. Pointers are just references to things, and you can use pointers to access things that are in other things' stack frames. So even though numbers is local to main, we can still access it through this pointer. But since it's just a pointer and it's just a reference, sizeof(haystack) just returns the size of the reference itself. It doesn't return the size of the thing it's pointing to. It doesn't return the actual size of numbers. And so this isn't going to work as we want it to. 

Questions on that? Pointers will be gone into in significantly more gory detail in weeks to come. And this is why a lot of things that you see, most search things or sort things, they're almost all going to need to take the actual size of the array, because in C, we have no idea what the size of the array is. You need to manually pass it in. And you can't manually pass in the entire array because you're just passing in the reference and it can't get the size from the reference. Okay. So now we want to implement what was explained before. You can work on it for a minute, and you don't have to worry about getting everything perfectly 100% working. Just write up the half pseudocode for how you think it should work. Okay. No need to be completely done with this yet. But does anyone feel comfortable with what they have so far, like something we can work with together? Does anyone want to volunteer? Or I will randomly pick. It doesn't have to be right by any measure but something we can modify into a working state. [student] Sure. >>Okay. So can you save the revision by clicking on the little Save icon. You're Ramya, right? >>[student] Yeah. >>[Bowden] Okay. So now I can view your revision and everyone can pull up the revision. And here we have-- Okay. So Ramya went with the recursive solution, which is definitely a valid solution. There are two ways you can do this problem. You can either do it iteratively or recursively. Most problems you encounter that can be done recursively can also be done iteratively. So here we've done it recursively. 

Does someone want to define what it means to make a function recursive? [student] When you have a function call itself and then call itself until it comes out with true and true. >>Yeah. A recursive function is just a function which calls itself. There are three big things that a recursive function must have. The first is obviously, it calls itself. The second is the base case. So at some point the function needs to stop calling itself, and that's what the base case is for. So here we know that we should stop, we should give up in our search when start equals end--and we'll go over what that means. But finally, the last thing that's important for recursive functions: the functions must somehow approach the base case. Like if you're not actually updating anything when you make the second recursive call, if you're literally just calling the function again with the same arguments and no global variables have changed or anything, you will never reach the base case, in which case that's bad. It will be an infinite recursion and a stack overflow. But here we see that the update is happening since we are updating start + end/2, we're updating the end argument here, we're updating the start argument here. So in all recursive calls we are updating something. Okay. Do you want to walk us through your solution? >>Sure. I'm using SearchHelp so that every time I make this function call I have the start of where I'm looking for in the array and the end of where I'm looking the array. 

At every step where it's saying it's the middle element, which is start + end/2, is that equal to what we're looking for? And if it is, then we found it, and I guess that gets passed up the levels of recursion. And if that's not true, then we check whether that middle value of the array is too big, in which case we look at the left half of the array by going from start to the middle index. And otherwise we do the end half. [Bowden] Okay. That sounds good. Okay, so a couple things, and actually, this is a very high-level thing that you will never need to know for this course, but it is true. Recursive functions, you always hear that they're a bad deal because if you recursively call yourself too many times, you get stack overflow since, as I said before, every function gets its own stack frame. So each call of the recursive function gets its own stack frame. So if you make 1,000 recursive calls, you get 1,000 stack frames, and quickly you lead to having too many stack frames and things just break. So that's why recursive functions are generally bad. But there is a nice subset of recursive functions called tail-recursive functions, and this happens to be an example of one where if the compiler notices this and it should, I think--in Clang if you pass it the -O2 flag then it will notice this is tail recursive and make things good. 

It will reuse the same stack frame over and over again for each recursive call. And so since you're using the same stack frame, you do not need to worry about ever stack overflowing, and at the same time, like you said before, where once you return true, then it has to return up all of these stack frames and the 10th call to SearchHelp has to return to the 9th, has to return to the 8th. So that doesn't need to happen when functions are tail recursive. And so what makes this function tail recursive is notice that for any given call to searchHelp the recursive call that it's making is what it's returning. So in the first call to SearchHelp, we either immediately return false, immediately return true, or we make a recursive call to SearchHelp where what we're returning is what that call is returning. And we could not do this if we did something like int x = SearchHelp, return x * 2, just some random change. 

So now this recursive call, this int x = SearchHelp recursive call, is no longer tail recursive because it actually does have to return back to a previous stack frame so that that previous call to the function can then do something with the return value. So this is not tail recursive, but what we had before is nicely tail recursive. Yeah. [student] Shouldn't the second base case be checked first because there could be a situation where when you pass it the argument you have start = end, but they are the needle value. The question was can't we run into the case where end is the needle value or start = end, appropriately, start = end and you haven't actually checked that particular value yet, then start + end/2 is just going to be the same value. But we've already returned false and we never actually checked the value. So at the very least, in the first call, if size is 0, then we want to return false. But if size is 1, then start isn't going to equal end, and we'll at least check the one element. But I think you are right in that we can end up in a case where start + end/2, start ends up being the same as start + end/2, but we never actually checked that element. 

So if we first check is the middle element the value we're looking for, then we can immediately return true. Else if they're equal, then there's no point in continuing since we're just going to update to a case where we are on a single-element array. If that single element is not the one we're looking for, then everything is wrong. Yeah. [student] The thing is that since size is actually larger than the number of elements in the array, there is already an offset-- >>So will size-- [student] Say if the array was size 0, then the SearchHelp will actually check haystack of 0 on the first call. The array has size 0, so the 0 is-- >>Yeah. There's another thing that--it might be good. Let's think. So if the array had 10 elements and the middle one we're going to check is index 5, so we're checking 5, and let's say that the value is less. So we're throwing everything away from 5 onward. So start + end/2 is going to be our new end, so yeah, it's always going to stay beyond the end of the array. If it's a case if it was even or odd, then we would check, say, 4, but we're still throwing away-- So yeah, end is always going to be beyond the actual end of the array. So the elements we are focusing on, end is always going to be the one after that. And so if start does ever equal end, we are in an array of size 0. 

The other thing I was thinking is we are updating start to be start + end/2, so this is the case that I'm having trouble with, where start + end/2 is the element we're checking. Let's say we had this 10-element array. Whatever. So start + end/2 is going to be something like this one, and if that's not the value, say we want to update. The value is greater, so we want to look at this half of the array. So how we're updating start, we're updating start to now be this element. But this may still work, or at the very least, you can do start + end/2 + 1. [student] You don't need to be start + end [inaudible] >>Yeah. We have already checked this element and know it's not the one we're looking for. So we don't need to update start to be this element. We can just skip it and update start to be this element. And is there ever a case, let's say, that this were end, so then start would be this, start + end/2 would be this, start + end-- Yeah, I think it can end up in infinite recursion. Let's say it's just an array of size 2 or an array of size 1. I think this will work. So currently, start is that element and end is 1 beyond it. So the element that we're going to check is this one, and then when we update start, we're updating start to be 0 + 1/2, which is going to end us back with start being this element. 

So we're checking the same element over and over again. So this is the case where every recursive call must actually update something. So we need to do start + end/2 + 1, or else there's a case where we're not actually updating start. Everyone see that? Okay. Does anyone have questions on this solution or any more comments? Okay. Does anyone have an iterative solution that we can all look at? Did we all do it recursively? Or also I guess if you opened hers, then you might have overridden your previous one. Does it automatically save? I'm not positive. Does anyone have iterative? We can walk through it together if not. The idea is going to be the same. Iterative solution. We're going to want to basically do the same idea where we want to keep track of the new end of the array and the new start of the array and do that over and over. And if what we're keeping track of as the start and the end ever intersect, then we did not find it and we can return false. So how do I do that? Anyone have suggestions or code for me to pull up? [student] Do a while loop. >>Yeah. You are going to want to do a loop. 

Did you have code I could pull up, or what were you going to suggest? [student] I think so. >>All right. This makes things easier. What was your name? [student] Lucas. Revision 1. Okay. Low is what we called start before. Up is not quite what we called end before. Actually, end is now within the array. It's an element we should consider. So low is 0, up is the size of the array - 1, and now we are looping, and we are checking-- I guess you can walk through it. What was your thinking through this? Walk us through your code. [student] Sure. Look at the haystack value in the middle and compare it to needle. So if it's greater than your needle, then you want to--oh, actually, that should be backwards. You're going to want to throw away the right half, and so yeah, that should be the way. [Bowden] So this should be less? Is that what you said? >>[student] Yeah. [Bowden] Okay. Less. So if what we're looking at is smaller than what we want, then yeah, we want to throw away the left half, which means we are updating everything we're considering by moving low to the right of the array. This looks good. I think it has the same issue that we said on the previous one, where if low is 0 and up is 1, then low + up/2 is going to set up to be the same thing again. 

And even if that's not the case, it is still more efficient at the very least to just throw away the element we just looked at which we know is wrong. So low + up/2 + 1-- >>[student] That should be the other way. [Bowden] Or this should be - 1 and the other one should be + 1. [student] And there should be a double equals sign. >>[Bowden] Yeah. [student] Yeah. Okay. And finally, now that we have this + 1 - 1 thing, is it--it might not be--is it ever possible for low to end up with a value greater than up? I think the only way that can happen-- Is it possible? >>[student] I don't know. But if it gets truncated and then gets minus that 1 and then-- >>Yeah. [student] It would possibly get messed up. I think it should be good only because for it to end up lower they would have to be equal, I think. But if they are equal, then we wouldn't have done the while loop to begin with and we just would have returned the value. So I think we're good now. Notice that even though this problem is no longer recursive, the same kind of ideas apply where we can see how this so easily lends itself to a recursive solution by the fact that we're just updating the indices over and over again, we're making the problem smaller and smaller, we're focusing on a subset of the array. [student] If low is 0 and up is 1, they would both be 0 + 1/2, which would go to 0, and then one would be + 1, one would be - 1. [student] Where are we checking equality? Like if the middle one is actually needle? We're not currently doing that? Oh! If it's-- Yes. We can't just do the test down here because let's say the first middle-- [student] It's actually like not throw away the bound. So if you throw away the bound, you have to check it first or whatever. Ah. Yeah. >>[student] Yeah. So now we have thrown away the one we currently looked at, which means we now need to also have if (haystack[(low+up)/2] == needle), then we can return true. And whether I put else or just if, it means literally the same thing because this would have returned true. So I'll put else if, but it doesn't matter. 

So else if this, else this, and this is a common thing I do where even if it is the case where everything is good here, like low can never be greater than up, it's not worth reasoning about whether that's true. So you may as well say while low is less than or equal to or while low is less than so if they are ever equal or low happens to pass up, then we can break out of this loop. Questions, concerns, comments? Okay. This looks good. Now we want to do sort. If we go to my second revision, we see these same numbers, but now they are no longer in sorted order. And we want to implement sort using any algorithm in O of n log n. So which algorithm do you think we should implement here? >>[student] Merge sort. [Bowden] Yeah. Merge sort is O(n log n), so that's what we're going to do. And the problem is going to be pretty similar, where it easily lends itself to a recursive solution. We can also come up with an iterative solution if we want, but recursion will be easier here and we should do recursion. I guess we will walk through merge sort first, although there is a lovely video on merge sort already. [laughter] So merge sort there are--I am wasting so much of this paper. Oh, there's only one left. So merge. Oh, 1, 3, 5. Okay. Merge takes two separate arrays. Individually those two arrays are both sorted. So this array, 1, 3, 5, sorted. This array, 0, 2, 4, sorted. Now what merge should do is combine them into a single array that is itself sorted. So we want an array of size 6 that is going to have these elements inside of it in sorted order. 

And so we can take advantage of the fact that these two arrays are sorted to do this in linear time, linear time meaning if this array is size x and this is size y, then the total algorithm should be O(x+y). Okay. So suggestions. [student] Could we start from the left? So you'll put the 0 down first and then the 1 and then here you're at the 2. So it's kind of like you have a tab that's moving to the right. >>[Bowden] Yeah. For both of these arrays if we just focus on the leftmost element. Because both arrays are sorted, we know that these 2 elements are the smallest elements in either array. So that means that 1 of those 2 elements must be the smallest element in our merged array. It just so happens that the smallest is the one on the right this time. So we take 0, insert it on the left because 0 is less than 1, so take 0, insert it into our first position, and then we update this to now focus on the first element. And now we repeat. So now we compare 2 and 1. 1 is smaller, so we'll insert 1. We update this pointer to point to this guy. Now we do it again, so 2. This will update, compare these 2, 3. This updates, then 4 and 5. So that is merge. 

It should be pretty obvious that it is linear time since we just go across each element once. And that is the biggest step to implementing merge sort is doing this. And it's not that hard. A couple things to worry about is let's say we were merging 1, 2, 3, 4, 5, 6. In this case we end up in the scenario where this one is going to be smaller, then we update this pointer, this one is going to be smaller, update this, this one's smaller, and now you have to recognize when you've actually run out of elements to compare with. Since we have already used this entire array, everything in this array is now just inserted into here. So if we ever run into the point where one of our arrays is completely merged already, then we just take all the elements of the other array and insert them into the end of the array. So we can just insert 4, 5, 6. Okay. That is one thing to watch out for. Implementing that should be step 1. Merge sort then based on that, it's 2 steps, 2 silly steps. Let's just give this array. So merge sort, step 1 is to recursively break the array into halves. So split this array into halves. We now have 4, 15, 16, 50 and 8, 23, 42, 108. And now we do it again and we split these into halves. I'll just do it on this side. So 4, 15 and 16, 50. We would do the same thing over here. And now we split it into halves again. And we have 4, 15, 16, 50. So that is our base case. Once the arrays are of size 1, then we stop with the splitting into halves. 

Now what do we do with this? We end up this will also break down into 8, 23, 42, and 108. So now that we're at this point, now step two of merge sort is just merging pairs to the lists. So we want to merge these. We just call merge. We know merge will return these in sorted order. 4, 15. Now we want to merge these, and that will return a list with those in sorted order, 16, 50. We merge those--I cannot write--8, 23 and 42, 108. So we have merged pairs once. Now we just merge again. Notice that each of these lists is sorted in itself, and then we can just merge these lists to get a list of size 4 which is sorted and merge these two lists to get a list of size 4 that is sorted. And finally, we can merge those two lists of size 4 to get one list of size 8 that is sorted. So to see that this is overall n log n, we already saw that merge is linear, so when we're dealing with merging these, so like the overall cost of merge for these two lists is just 2 because-- Or well, it's O of n, but n here is just these 2 elements, so it's 2. And these 2 will be 2 and these 2 will be 2 and these 2 will be 2, so across all of the merges that we need to do, we end up doing n. Like 2 + 2 + 2 + 2 is 8, which is n, so the cost of merging in this set is n. And then the same thing here. We'll merge these 2, then these 2, and individually this merge will take four operations, this merge will take four operations, but once again, between all of these, we end up merging n total things, and so this step takes n. And so each level takes n elements being merged. 

And how many levels are there? At each level, our array grows by size 2. Here our arrays are of size 1, here they're of size 2, here they're of size 4, and finally, they're of size 8. So since it is doubling, there are going to be a total of log n of these levels. So with log n levels, each individual level taking n total operations, we get an n log n algorithm. Questions? Have people already made progress on how to implement this? Is anyone already in a state where I can just pull up their code? I can give a minute. This one is going to be longer. I highly recommend recur-- You don't have to do recursion for merge because to do recursion for merge, you're going to have to pass a bunch of different sizes. You can, but it's annoying. But recursion for sort itself is pretty easy. You just literally call sort on left half, sort on right half. Okay. Anyone have anything I can pull up yet? Or else I'll give a minute. Okay. Anyone have something we can work with? Or else we'll just work with this and then expand from there. 

Anyone have more than this that I can pull up? [student] Yeah. You can pull up mine. >>All right. Yes! [student] There were a lot of conditions. >>Oh, shoot. Can you-- [student] I have to save it. >>Yeah. So we did do the merge separately. Oh, but it's not that bad. Okay. So sort is itself just calling mergeSortHelp. Explain to us what mergeSortHelp does. [student] MergeSortHelp pretty much does the two main steps, which is to sort each half of the array and then to merge both of them. [Bowden] Okay, so give me a second. I think this-- >>[student] I need to-- Yeah. I'm missing something. In merge, I realize that I need to create a new array because I couldn't do it in place. >>Yes. You cannot. Correct. [student] So I create a new array. I forgot at the end of merge to re-change. Okay. We need a new array. In merge sort, this is almost always true. Part of the cost of a better algorithm time-wise is almost always needing to use a bit more memory. So here, no matter how you do merge sort, you would inevitably need to use some extra memory. He or she created a new array. And then you say at the end we just need to copy new array into the original array. [student] I think so, yeah. I don't know if that works in terms of counting by reference or whatever-- Yeah, it will work. >>[student] Okay. Did you try running this? >>[student] No, not yet. >>Okay. Try running it, and then I'll talk about it for a second. [student] I need to have all the function prototypes and everything, though, right? The function prototypes. Oh, you mean like-- Yes. Sort is calling mergeSortHelp. 

So in order for sort to call mergeSortHelp, mergeSortHelp must either have been defined before sort or we just need the prototype. Just copy and paste that. And similarly, mergeSortHelp is calling merge, but merge has not been defined yet, so we can just let mergeSortHelp know that that's what merge is going to look like, and that's that. So mergeSortHelp. We have an issue here where we have no base case. MergeSortHelp is recursive, so any recursive function is going to need some sort of base case to know when to stop recursively calling itself. What is our base case going to be here? Yeah. [student] If the size is 1? >>[Bowden] Yes. So like we saw right there, we stopped splitting arrays once we got into arrays of size 1, which inevitably are sorted themselves. So if size equals 1, we know the array is already sorted, so we can just return. 

Notice that's void, so we don't return anything particular, we just return. Okay. So that's our base case. I guess our base case could also be if we happen to be merging an array of size 0, we probably want to stop at some point, so we can just say size less than 2 or less than or equal to 1 so that this will work for any array now. Okay. So that's our base case. Now do you want to walk us through merge? What do all these cases mean? Up here, we're just doing the same idea, the-- [student] I need to be passing size with all the mergeSortHelp calls. I added size as an additional primary and it's not there, like size/2. [Bowden] Oh, size/2, size/2. >>[student] Yeah, and also in the above function as well. [Bowden] Here? >>[student] Just size. >>[Bowden] Oh. Size, size? >>[student] Yeah. [Bowden] Okay. Let me think for a second. Do we run into an issue? We're always treating the left as 0. >>[student] No. That's wrong too. Sorry. It should be start. Yeah. [Bowden] Okay. I like that better. And end. Okay. So now do you want to walk us through merge? >>[student] Okay. I'm just walking through this new array that I've created. Its size is the size of the portion of the array that we want to be sorted and trying to find the element that I should put in the new array step. So to do that, first I'm checking if the left half of the array continues to have any more elements, and if it doesn't, then you go down to that else condition, which just says okay, it must be in the right array, and we'll put that in the current index of newArray. 

And then otherwise, I'm checking if the right side of the array is also finished, in which case I just put in the left. That might not actually be necessary. I'm not sure. But anyway, the other two check which of the two are smaller in the left or the right. And also in each case, I'm incrementing whichever placeholder I increment. [Bowden] Okay. That looks good. Does anyone have comments or concerns or questions? So the four cases that we have to bring things into just being--or it looks like five-- but we have to consider whether the left array has run out of things we need to merge, whether the right array has run out of things we need to merge-- I'm pointing at nothing. So whether the left array has run out of things or the right array has run out of things. Those are two cases. We also need the trivial case of whether the left thing is less than the right thing. Then we want to choose the left thing. Those are the cases. So this was right, so that's that. Array left. It's 1, 2, 3. Okay. So yeah, those are the four things we might want to do. And we won't go over an iterative solution. I would not recommend-- Merge sort is an example of a function that is both not tail recursive, it's not easy to make it tail recursive, but also it's not very easy to make it iterative. This is very easy. This implementation of merge sort, merge, no matter what you do, you're going to build merge. 

So merge sort built on top of merge recursively is just these three lines. Iteratively, it is more annoying and more difficult to think about. But notice that it's not tail recursive since mergeSortHelp--when it calls itself-- it still needs to do things after this recursive call returns. So this stack frame must continue to exist even after calling this. And then when you call this, the stack frame must continue to exist because even after that call, we still need to merge. And it is nontrivial to make this tail recursive. Questions? All right. So going back to sort--oh, there's two things I want to show. Okay. Going back to sort, we'll do this quickly. Or search. Sort? Sort. Yeah. Going back to the beginnings of sort. We want to create an algorithm that sorts the array using any algorithm in O of n. So how is this possible? Does anyone have any sort of-- I hinted before at-- If we're about to improve from n log n to O of n, we have improved our algorithm time-wise, which means what are we going to need to do to make up for that? [student] Space. >>Yeah. We're going to be using more space. And not even just more space, it's exponentially more space. So I think this type of algorithm is pseudo something, pseudo polynom-- pseudo-- I can't remember. Pseudo something. But it's because we need to use so much space that this is achievable but not realistic. 

And how do we achieve this? We can achieve this if we guarantee that any particular element in the array is below a certain size. So let's just say that size is 200, any element in an array is below size 200. And this is actually very realistic. You can very easily have an array that you know everything in it is going to be less than some number. Like if you have some absolutely massive vector or something but you know everything is going to be between 0 and 5, then it's going to be significantly faster to do this. And the bound on any of the elements is 5, so this bound, that is how much memory you're going to be using. So the bound is 200. In theory there is always a bound since an integer can only be up to 4 billion, but that's unrealistic since then we'd be using space on the order of 4 billion. So that's unrealistic. But here we'll say our bound is 200. The trick to doing it in O of n is we make another array called counts of size BOUND. So actually, this is a shortcut for--I actually don't know if Clang does this. But in GCC at the very least--I'm assuming Clang does it too-- this will just initialize the entire array to be 0s. So if I don't want to do that, then I could separately do for (int i = 0; i < BOUND; i++) and counts[i] = 0; So now everything is initialized to 0. I iterate over my array, and what I'm doing is I'm counting the number of each-- Let's go down here. We have 4, 15, 16, 50, 8, 23, 42, 108. What I'm counting is the number of occurrences of each of those elements. Let's actually add a couple more in here with some repeats. So the value we have here, the value of that is going to be array[i]. So val could be 4 or 8 or whatever. And now I'm counting how many of that value I've seen, so counts[val]++; After this is done, counts is going to look something like 0001. Let's do counts[val]-- BOUND + 1. 

Now that's just to account for the fact that we're starting from 0. So if 200 is going to be our largest number, then 0 to 200 is 201 things. So counts, it'll look like 00001 because we have one 4. Then we'll have 0001 where we'll have a 1 in the 8th index of count. We'll have a 2 in the 23rd index of count. We'll have a 2 in the 42nd index of count. So we can use count. So num_of_item = counts[i]. And so if num_of_item is 2, that means we want to insert 2 of the number i into our sorted array. So we need to keep track of how far we are into the array. So index = 0. Array-- I'll just write it. Counts-- array[index++] = i; Is that what I want? I think that's what I want. Yes, this looks good. Okay. So does everyone understand what the purpose of my counts array is? It is counting the number of occurrences of each of these numbers. Then I am iterating over that counts array, and the ith position in the counts array is the number of i's that should appear in my sorted array. That's why counts of 4 is going to be 1 and counts of 8 is going to be 1, counts of 23 is going to be 2. So that's how many of them I want to insert into my sorted array. Then I just do that. I am inserting num_of_item i's into my sorted array. 

Questions? And so again, this is linear time since we are just iterating over this once, but it's also linear in what this number happens to be, and so it heavily depends on what your bound is. With a bound of 200, that's not that bad. If your bound is going to be 10,000, then that's a little worse, but if your bound is going to be 4 billion, that's completely unrealistic and this array is going to have to be of size 4 billion, which is unrealistic. So that's that. Questions? [inaudible student response] >>Okay. I realized one other thing when we were going through. I think the problem was in Lucas's and probably every single one we've seen. I completely forgot. The only thing I wanted to comment on is that when you're dealing with things like indices, you never really see this when you're writing a for loop, but technically, whenever you're dealing with these indices, you should pretty much always deal with unsigned integers. The reason for this is when you're dealing with signed integers, so if you have 2 signed integers and you add them together and they end up too big, then you end up with a negative number. So that's what integer overflow is. 

If I add 2 billion and 1 billion, I end up with negative 1 billion. That's how integers work on computers. So the problem with using-- That's fine except if low happens to be 2 billion and up happens to be 1 billion, then this is going to be negative 1 billion and then we're going to divide that by 2 and end up with negative 500 million. So this is only an issue if you happen to be searching through an array of billions of things. But if low + up happens to overflow, then that's a problem. As soon as we make them unsigned, then 2 billion plus 1 billion is 3 billion. 3 billion divided by 2 is 1.5 billion. So as soon as they're unsigned, everything is perfect. And so that's also an issue when you're writing your for loops, and actually, it probably does it automatically. It will actually just yell at you. So if this number is too big to be in just an integer but it would fit in an unsigned integer, it will yell at you, so that's why you never really run into the issue. You can see that an index is never going to be negative, and so when you're iterating over an array, you can almost always say unsigned int i, but you don't really have to. Things are going to work pretty much just as well. Okay. [whispers] What time is it? The last thing I wanted to show--and I'll just do it really quick. You know how we have #define so we can #define MAX as 5 or something? Let's not do MAX. #define BOUND as 200. That's what we did before. That defines a constant, which is just going to be copied and pasted wherever we happen to write BOUND. 

So we can actually do more with #defines. We can #define functions. They're not really functions, but we'll call them functions. An example would be something like MAX(x, y) is defined as (x < y ? y : x). Okay. So you should get used to ternary operator syntax, but is x less than y? Return y, else return x. So you can see you can make this a separate function, and the function could be like bool MAX takes 2 arguments, return this. This is one of the most common ones I see done like this. We call them macros. This is a macro. This is just the syntax for it. You can write a macro to do whatever you want. You frequently see macros for debugging printfs and stuff. So a type of printf, there are special constants in C like underscore LINE underscore, 2 underscores LINE underscore, and there's also I think 2 underscores FUNC. That might be it. Something like that. Those things will be replaced with the name of the function or the number of the line that you're on. Frequently, you write debugging printfs that down here I could then just write DEBUG and it will print the line number and function that I happen to be in that it encountered that DEBUG statement. And you can also print other things. So one thing you should watch out for is if I happen to #define DOUBLE_MAX as something like 2 * y and 2 * x. So for whatever reason, you happen to do that a lot. So make it a macro. This is actually broken. I would call it by doing something like DOUBLE_MAX(3, 6). So what should be returned? [student] 12. Yes, 12 should be returned, and 12 is returned. 3 gets replaced for x, 6 gets replaced for y, and we return 2 * 6, which is 12. Now what about this? What should be returned? [student] 14. >>Ideally, 14. The issue is that how hash defines work, remember it's a literal copy and paste of pretty much everything, so what this is going to be interpreted as is 3 less than 1 plus 6, 2 times 1 plus 6, 2 times 3. 

So for this reason you almost always wrap everything in parentheses. Any variable you almost always wrap in parentheses. There are cases where you don't have to, like I know that I don't need to do that here because less than is pretty much always just going to work, although that might not even be true. If there is something ridiculous like DOUBLE_MAX(1 == 2), then that's going to get replaced with 3 less than 1 equals equals 2, and so then it's going to do 3 less than 1, does that equal 2, which is not what we want. So in order to prevent any operator precedence problems, always wrap in parentheses. Okay. And that's it, 5:30. If you have any questions on the pset, let us know. It should be fun, and the hacker edition also is much more realistic than the hacker edition of last year's, so we hope that a lot of you try it. Last year's was very overwhelming. 

[CS50.TV]