Tip:
Highlight text to annotate it
X
Okay. So in this video we'll get our first sense of what it's actually like to
analyze an algorithm and we'll do that by first of all reviewing a famous sorting
algorithm, namely the merge sort algorithm. And then giving a really fairly
mathematically precise upper bound on exactly how many operations the merge sort
algorithm requires to correctly sort an input array. So I feel like I should begin
with a bit of an apology. Here we are in 2012, a very futuristic sounding date. And
yet I'm beginning with a really quite ancient algorithm. So for example, Merge
Sort was certainly known, to John Von Norman all the way back in 1945. So, what
justification do I have for beginning, you know, a modern class in algorithms with
such an old example? Well, there's a bunch of reasons. One, I haven't even put down
on the slide, which is like a number of the [inaudible] we'll see, emerged forth
as an oldie but a goo die. So it's over 60, or maybe even 70 years old. But it's
still used all the time in practice, cuz this really is one of the methods of
choice, for sorting. The standard sorting algorithm in the number of programming
libraries. So that's the first reason. But there's a number of others as well that I
want to be explicit about. So first of all, Throughout these online courses we'll
see a number of general algorithm design paradigms ways of solving problems that
cut across different application domains and the first one we're going to focus on
is called the divide and conquer algorithm design paradigm so in divide and conquer
the idea is you take a problem you break it down into smaller sub problems which
you solve recursively and then you somehow combine the results of the smaller
sub-problem to get a solution. The original problem that you actually cared
about and merge Sort is still to this day the perhaps the most transparent
application of the divide and conquer paradigm, it will just be very clear what
the paradigm is what analysis and challenge it presents and what kind of
benefits you might derive as far as the benefits so for example you're probably
all aware of the sorting problem probably you know some number of sorting algorithms
perhaps including merge Sort itself and merge Sort is better than a lot of this
sort of simpler I would say obvious sorting algorithms so for example three
other sorting algorithms that you may know about but that I'm not going to discuss
here. If you don't know them I encourage you to look them up in a text book or look
them up on the web but so three starting algorithms which are perhaps simpler first
of all is selection sort so this is where you do a number of passes through the way
repeatedly identifying the minimum of the elements that you haven't looked at yet so
you're basically a linear number of passes each time doing a minimum computation,
there's insertion sort which is still useful in certain practices as we will
discuss but again it's generally not as good as merge Sort where again you just
maintain the invariant that the prefix of array is assorted version of those
elements so after. Ten loops of insertion sort you'll have the invariant that
whatever the first ten elements of the array are they're going to be in sorted
order and then when insertion [inaudible] completes you have an entire sorted array.
Finally some of you may know about bubble sort this is where you identify adjacent
pairs of elements which are out of order and then you do repeated swaps until in
the end the array is completely sorted. Again I just say this to jog your memory,
these are simpler sorts than merge sort but all of them are worse in the sense
they all have performance in general which scales with N squared and the input array
has N elements so they all have in some sense quadratic running time. But if we
use this non-trivial divide and conquer approach, or non-obvious approach, we'll
get a, as we'll see, a much better running time than this quadratic dependence on the
input. Okay? So we'll get a win. First awarding in divide and conquer and
[inaudible] then realizes that benefit. So the second reason that I wanna start out
by talking about the Merge Sort algorithm, is to help you calibrate your preparation.
I think the discussion we're about to have will give you a good signal for whether
you're background's at about the right level, of the audience that I'm thinking
about for this course. So in particular, when I describe the Merge Sort algorithm.
You'll notice that I'm not going to describe in a level of detail that you can
just translate it line by line into a working program in some programming
language. My assumption again is that you're a sought enough programmer you can
take the idea of the algorithm how it works and you're perfectly capable of
[inaudible] turning that into a working program of whatever language you see fit.
So hopefully I don't you know it may not be easy the analysis of merge [inaudible]
the discussion of merge [inaudible] but I hope that you find it at least relatively
straight forward because as the course moves on we're going to be discussing
algorithms and analysis which are a bit more complicated than the one we're
[inaudible]. [inaudible] Sort. So in other words, I think that this would be a good
warm-up for what's to come. Now another reason I want to discuss [inaudible] is
that our analysis of it will naturally say [inaudible] discussion of how we. Analyze
the algorithms in this course and in general, so we're going to expose a couple
of assumptions in our analysis we'll focus on worst case behavior we'll look for
guarantees on performance on running time that hold for every possible input on a
given size and then we'll also expose our focus on so called [inaudible] analysis
meaning we'll be much more concerned with the rate of growth on an algorithms
performance than on things like low overturns or on small changes in the
constant factors. Finally. We'll do, the analysis of Merge Sort using what's called
a recursion tree method. So this is a way of tallying up the total number of
operations that are executed by an algorithm. And as we'll see a little bit
later, this recursion treatment method generalizes greatly. And it will allow us
to analyze lots of different recursive algorithms, lots of different divide and
conquer algorithms, including the integer multiplication algorithm that we
discussed, in an earlier segment. So those are the reasons to start out with Merge
Sort. So what is the computational problem that Merge Sort is meant to solve? Well,
presumably, you all know about the sorting problem. But let me tell you a little bit
about it anyways, just so that we're all on the same page. So, we're given as
input. An array of n numbers in arbitrary order, and the goal of course is to
produce output array where the numbers are in Sorter order, let's say from smallest
to largest. Okay so, for example, we could consider the following input array, and
the goal would be to produce the following output array. Now one quick comment you'll
notice that here in the input array, it had eight elements and all of them were
distinct it was the different integers between one and eight. Now the sorting
problem really isn't any harder if you have duplicates, in fact it can even be
easier, but to keep the discussion as simple as possible let's just. Among
friends, go ahead and assume that their distinct for the purpose of this lecture.
And I'll leave it as an exercise which I encourage you to do, which is to think
about how the merge sort algorithm. Implementation and analysis would be
different, if at all, if there were Thomas, okay? Go ahead and make the
[inaudible] assumption for simplicity from here on out. Okay, so before I write down
any pseudo code for [inaudible], let me just show you how the algorithm works
using a picture and I think it'll be pretty clear what the code would be even
just given a single example. So let's go ahead and consider the same unsorted input
array that we had on the previous slide. So the merge sort algorithm is a recursive
algorithm and again that means that a program which calls itself and it calls
itself on smaller sub problems of the same form. Okay? So the merge sort is its
purpose in life is to sort the given input array so it's going to spawn of cause of
itself on smaller arrays. And this is gonna be a connanicle divide and conquer
application where we simply take the input array, we split it in half, we solve the
left have for cursive [inaudible], we solve the right have for cursive
[inaudible], and then we combine the results. So let's look at that in the
picture. So the first recursive call gets the first four elements, the left half of
the array. Namely five, four, one, and 8's. And, of course, the other recursive
call is gonna get the rest of the elements, seven, two, six, and three. You
can imagine these as being copied into new arrays before they're given to the
recursive calls. Now, by the magic of recursion, or by induction, if you like,
the recursive calls will do their task. They will correctly sort each of these
arrays of four elements. And we'll get back sorted versions of them. So from our
first recursive call, we receive the output, one, four, five, eight. And from
the second recursive call, we received the sort it out. But two, three, six, seven.
So now, all that remains to complete the Merge Sort is to take the two results of
our recursive calls, these two sorted elements of [inaudible] four and combine
them to produce the final output. Namely the sorted array of all eight of the input
numbers. And this is the step which is called the merge. And hopefully you are
already are thinking about how you might actually implement this merge in a
computationally efficient way. But I do owe you some more details. And I will tell
you exactly how the merge is done. In effect, you just walk corners down each of
the two sort of sub-arrays, copying over, populating the output array in the.