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.