00:00:00,060 --> 00:00:02,060 DAVID MALAN: --you can leverage both intuitively and in code to implement this new and improved fourth algorithm. DOUG LLOYD: After finally having hinted about it now by talking about all these other algorithms, we finally introduce something that's better, objectively better, in a worst case. DAVID MALAN: Yeah, in most cases, frankly. Yeah, when I took CS50 we use Quicksort which never clicked for me in quite the same way. Merge sort has always seemed a little simpler conceptually, if a little more magical, given that it really reduces to this recursive definition. And frankly this is why we deliberately introduce recursion at this point in the course, even though we don't use it all that much in C we introduced the idea of it so that we can really introduce a recursive algorithm like this. DOUG LLOYD: It was interesting though. One of the things that we got some of the most demand for from our online audience was to have a video Quicksort, even though we don't teach it in the class, it's actually one of the few topics that we have a short for that we never actually use. I agree though, I think that the concept of a pivot and having all these-- it's so many extra layers to try to boil down to this. DAVID MALAN: And I think we've gotten better at the presentation of this, like last year in particular I spent a while coming up with the simplified animation of merge sort just using excruciatingly detailed keynote slides like these, where they're very simple, but stepwise I mean there's dozens of slides that sort of give us this fake animation here that we can step through it at our own pace without having to just hit play and follow along. And these numbers too are sort of chosen. I accidentally have kept the even numbers on the left and the odd numbers on the right, but they do lend themselves in this order at least, to nice merging. And hopefully this helps students see, especially since the height of what we're about to do ultimately, or the number of vertical steps so to speak, ends up being logarithmic in height, three for eight elements, and meanwhile the length of these things, the number of elements we need to look at on each iteration is n, and therein lies are n log n. DOUG LLOYD: Yeah, I think it was last year was the first time we had this sort of visualization. And I think that that was a key turning point in making that n and the log n, I think, actually meaningful for perhaps the first time. DAVID MALAN: Yeah, hopefully. DOUG LLOYD: Because log of eight is 3 and so you can actually finally now see these, were that eight and that three, or that n and that log n come from. DAVID MALAN: But there too, for students for whom the mathematics come a little more comfortably-- and it's actually very nicely defined in terms of its recursive formula, whereby you can abstract away what the running time is and actually see formulaic what it is. And so long as you know or can look up in the back of a math or physics textbook the sort of summation that that series will give you, then you can see the n log n popping out of the total running time. DOUG LLOYD: Is there a reason that we don't expect merge sort of students? None of our problem sets require it. DAVID MALAN: No, really probably for lack of time and a piece set. We've generally had students do something like linear search or binary search because those are nice stepping stones, and then sometimes A sorting algorithm. But we typically have combined our look at algorithms and sorting with something that involves distribution code like m of 15, for instance, most recently. And so it's really I think for just lack of enough time in the week, but I think that could certainly be factored out as a problem or set of problems unto itself. With that said, the problem with a lot of these canonical searching and sorting algorithms is that there's just so many solutions out there and it's not that I worry about issues of honesty here, it's just if you're googling around trying to understand bubble sort, or selection sort, or merge sort, or whatever better, odds are you're going to see minimally pseudo code in the explanation, which is great, but it's so much easier sometimes to explain an algorithm by way of its actual code when it really is only a few lines maybe a dozen or so lines. DOUG LLOYD: Yeah, its' not all that intellectually interesting to say implement this sort, right? DAVID MALAN: No, I'd rather they use it. DOUG LLOYD: It's only in the context of something else. DAVID MALAN: Exactly, otherwise it's a pretty mundane exercise. I think it's helpful, especially when you have to wrestle with issues of like rounding if you have an odd number of elements, like do you go left, do you go right, do you truncate or round up, but even that's like-- If you're going to try to understand the topic better you're probably going to see it anyway, at which point the opportunity is lost. So we focus, I think, on slightly more involved algorithms when we have students implement them.