0:00

Okay, so let's move on, and actually discuss the pseudo-code for the

merge sort algorithm. First, let me just tell you the pseudo-code, leaving aside

exactly how the merging subroutine is implemented. And thus, high levels should

be very simple and clear at this point. So there's gonna be two recursive calls, and

then there's gonna be a merging step. Now, I owe you a few comments, 'cause I'm being

a little sloppy. Again, as I promised, this isn't something you would directly

translate into code, although it's pretty close. But so what are the couple of the

ways that I'm being sloppy? Well, first of all, there's, [inaudible], you know, in

any recursive algorithm, you gotta have some base cases. You gotta have this idea

that when the input's sufficient. Really small you don't do any recursion, you just

return some trivial answer. So in the sorting problem the base case would be if

your handed an array that has either zero or an elements, well it's already sorted,

there's nothing to do, so you just return it without any recursion. Okay, so to be

clear, I haven't written down the base cases. Although of course you would if you were

actually implementing, a merge short. Some of you, make a note of that. A couple of

other things I'm ignoring. I'm ignoring what the, what to do if the array has odd

lengths, so if it has say nine elements, obviously you have to somehow break that

into five and four or four and five, so you would do that just in either way and

that would fine. And then secondly, I'm ignoring the details or what it really

means to sort of recursively sort, so for example, I'm not discussing exactly how

you would pass these subarrays onto the recursive calls. That's something that

would really depend somewhat on what, on the programming language, so that's

exactly what I want to avoid. I really want to talk about the concepts which

transcend any particular programming language implementation. So that's why I'm

going to describe algorithms at this level okay. Alright, so the hard part relatively

speaking, that is. How do you implement the merge depth? The recursive calls have

done their work. We have these two sort of separated half the numbers. The left half

and the right half. How do we combine them into one? And in English, I already told

you on the last slide. The idea is you just populate the output array in a sorted

order, by traversing pointers or just traversing through the two, sorted

sub-arrays in parallel. So let's look at that in some more detail. Okay, so here is

the pseudo-code for the merge step. [sound] So let me begin by, introducing

some names for the, characters in the, what we're about to discuss. So let's use

C. To denote the output array. So this is what we're suppose to spit out with the

numbers in sorted order. And then, I'm gonna use a and b to denote the results of

the two recursive calls, okay? So, the first recursive call has given us array a,

which contains the left half of the input array in sorted order. Similarly, b

contains the right half of the input array, again, in sorted order. So, as I

said, we're gonna need to traverse the two, sorted sub-arrays, a and b, in

parallel. So, I'm gonna introduce a counter, i, to traverse through a, j to

traverse through b. I and j will both be initialized to one, to be at the beginning

of their respective arrays. And now we're gonna do. We're going to do a single pass

of the output array copying it in an increasing order. Always taking the

smallest from the union of the two sorted sub arrays. And if you, if there's one

idea in this merge step it's just the realization that. The minimum element that

you haven't yet looked at in A and B has to be at the front of one or the two lists

right so for example at the very beginning of the algorithm where is the minimum

element over all. Well, which ever of the two arrays it lands in -- A or B -- it has to be

the smallest one there okay. So the smallest element over all is either the

smallest element A or it's the smallest element B. So you just check both places,

the smaller one is the smallest you copy it over and you repeat. That's it. So the

purpose of K is just to traverse the output array from left to right. That's

the order we're gonna populate it. Currently looking at position I, and the

first array of position J and the second array. So that's how far we've gotten, how

deeply we've probed in the both of those two arrays. We look at which one has the

current smallest, and we copy the smallest one over. Okay? So if the, if, the entry

in the i position of A is smaller, we copy that one over. Of course, we have to

increment i. We probe one deeper into the list A, and symmeterically for the case

where the current position in B has the smaller element. Now again, I'm being a

little bit sloppy, so that we can focus on the forest, and not sort of, And not get

bogged down with the trees. I'm ignoring some end cases, so if you really wanted to

implement this, you'd have to add a little bit, to keep track of when you fall off,

either, either A or B. Because you have additional checks for when i or j reaches

the end of the array, at which point you copy over all the remaining elements into

C. Alright, so I'm gonna give you a cleaned up version, of, that pseudo-code

so that you don't have to tolerate my questionable handwriting any longer than

is absolutely necessary. This again, is just the same thing that we wrote on the

last slide, okay? The pseudo-code for the merge step. Now, so that's the Merge Sort

algorithm. Now let's get to the meaty part of this lecture, which is, okay, so merge

sort produces a sorted array. What makes it, if anything, better than much simpler

non divide and conquer algorithms, like say, insertion sort? Other words, what is

the running time of the merge sort algorithm? Now I'm not gonna give you a

completely precise definition, definition of what I mean by running time and there's

good reason for that, as we'll discuss shortly. But intuitively, you should think

of the running time of an algorithm, you should imagine that you're just running

the algorithm in a debugger. Then, every time you press enter, you advance with one

line of the program through the debugger. And then basically, the running time is

just a number of operations executed, the number of lines of code executed. So the

question is, how many times you have to hit enter on the debugger before the,

program finally terminates. So we're interested in how many such, lines of code

get executed for Merge Short when an input array has n numbers. Okay, so

that's a fairly complicated question. So let's start with a more modest school.

Rather than thinking about the number of operations executed by Merge Sort, which

is this crazy recursive algorithm, which is calling itself over and over and over

again. Let's just think about how many operations are gonna get executed when we

do a single merge of two sorted sub arrays. That seems like it should be an

easier place to start. So let me remind you, the pseudo code of the merge

subroutine, here it is. So let's just go and count up how many operations

that are gonna get used. So there's the initialization step. So let's say that

I'm gonna charge us one operation for each of these two initializations. So let's

call this two operations, just set i equal to one and j equal to one then we have this four

loop executes a total number of end times so each of these in iterations of this

four loop how many instructions get executed, well we have one here we have a

comparison so we compare A(i) to B(j) and either way the comparison comes up we then

do two more operations, we do an assignment. Here or here. And then we do

an increment of the relevent variable either here or here. So that's gonna be

three operations per iteration. And then maybe I'll also say that in order to

increment K we're gonna call it a fourth iteration. Okay? So for each of these N

iterations of the four loop we're gonna do four operations. All right? So putting it

all together, what do we have is the running time for merge. So let's see the

upshot. So the upshot is that the running time of the merge subroutine, given an

array of M numbers, is at most four M plus two. So a couple of comments. First of

all, I've changed a letter on you so don't get confused. In the previous slide we

were thinking about an input size of N. Here I've just made it. See I've changed

the name of the variable to M. That's gonna be convenient once we think about

merge sort, which is recursing on smaller sub-problems. But it's exactly the same

thing and, and whatever. So an array of M entries does as most four M plus two.

Lines of code. The second thing is, there's some ambiguity in exactly how we

counted lines of code on the previous slide. So maybe you might argue that, you

know, really, each loop iteration should count as two operations, not just

one.'Cause you don't just have to increment K, but you also have to compare

it to the, upper bound of N. Eh, maybe. Would have been 5M+2 instead of 4M+2. So

it turns out these small differences in how you count up. The number of lines of

code executed are not gonna matter, and we'll see why shortly. So, amongst

friends, let's just agree, let's call it 4M plus two operations from merge, to

execute on array on exactly M entries. So, let me abuse our friendship now a little

bit further with an, an inequality which is true, but extremely sloppy. But I promise

it'll make our lives just easier in some future calculations. So rather than 4m+2,

'cause 2's sorta getting on my nerves. Let's just call this. Utmost six N.

Because m is at least one. [sound] Okay, you have to admit it's true, 6MO is at

least 4M plus two. It's very sloppy, these numbers are not anything closer to each

other for M large but, let's just go ahead and be sloppy in the interest of future

simplicity. Okay. Now I don't expect anyone to be impressed with this rather

crude upper bound, the number of lines of code that the merge subroutine needs to

finish, to execute. The key question you recall was how many lines of code does

merge sort require to correctly sort the input array, not just this subroutine. And

in fact, analyzing Merge Sort seems a lot more intimidating, because if it keeps

spawning off these recursive versions of itself. So the number of recursive calls,

the number of things we have to analyze, is blowing up exponentially as we think

about various levels of the recursion. Now, if there's one thing we have going

for us, it's that every time we make a recursive call. It's on a quite a bit

smaller input then what we started with, it's on an array only half the size of the

input array. So there's some kind of tension between on the one hand explosion

of sub problems, a proliferation of sub problems and the fact that successive

subproblems only have to solve smaller and smaller subproblems. And resolute

resolving these two forces is what's going to drive our analysis of Merge Short. So,

the good news is, is I'll be able to show you a complete analysis of exactly how

many lines of code Merge Sort takes. And I'll be able to give you, and, in fact, a

very precise upper bound. And so here's gonna be the claim that we're gonna prove

in the remainder of this lecture. So the claim is that Merge Short never needs than

more than six times N. Times the logarithm of N log base two if you're keeping track

plus an extra six N operations to correctly sort an input array of N

numbers, okay so lets discuss for a second is this good is this a win, knowing that

this is an upper bound of the number of lines of code the merger takes well yes it

is and it shows the benefits of the divide and conquer paradigm. Recall. In the

simpler sorting methods that we briefly discussed like insertion sort, selection

sort, and bubble sort, I claimed that their performance was governed by the

quadratic function of the input size. That is they need a constant times in the

squared number of operations to sort an input array of length N. Merge sort by

contrast needs at most a constant times N times log N, not N squared but N times

log N lines of code to correctly sort an input array. So to get a feel for what

kind of win this is let me just remind you for those of you who are rusty, or for

whatever reason have lived in fear of a logarithm, just exactly what the logarithm

is. Okay? So. The way to think about the logarithm is as follows. So you have the X

axis, where you have N, which is going from one up to infinity. And for

comparison let's think about just the identity function, okay? So, the function

which is just. F(n)=n. Okay, and let's contrast this with a logarithm. So

what is the logorithm? Well, for our purposes, we can just think of a logorithm

as follows, okay? So the log of n, log base 2 of n is, you type the number N

into your calculator, okay? Then you hit divide by two. And then you keep repeating

dividing by two and you count how many times you divide by two until you get a

number that drops below one okay. So if you plug in 32 you got to divide five

times by two to get down to one. Log base two of 32 is five. You put in 1024 you have to

divide by two, ten times till you get down to one. So log base two of 1024 is ten and

so on, okay. So the point is you already see this if a log of a 1000 roughly is

something like ten then the logarithm is much, much smaller than the input.

So graphically, what the logarithm is going to look like is it's going to look like. A

curve becomes very flat very quickly, as N grows large, okay? So F(n) being log

base 2 of n. And I encourage you to do this, perhaps a little bit more

precisely on the computer or a graphing calculator, at home. But log is

running much, much, much slower than the identity function. And as a result,

sorting algorithm which runs in time proportional to n times log n is much,

much faster, especially as n grows large, than a sorting algorithm with a

running time that's a constant times n squared.