Video 3-2: §3.1 Mergesort

0:00 <Untitled Chapter 1>

0:02 foreign let's have a look at merge swords maybe the most most classical among the efficient ones and certainly older than computers themselves um let's keep the phones out while you're at it

0:28 this is slightly more tricky so maybe it read a little careful yeah um Let me let me shortcut it I mean I'll leave it open for you to cast your voice but sad it's quite um quite clear that most of you have seen this before

1:32 so indeed merge sort is based on this principle of sorting the left half sorting the right half and then getting the two sorted halves somehow merged hence the name so let me just recap how merging Works in detail on a very small example uh I like this kind of pictographical representation it's nice and concise so that's the sorted left half sorted right half and you want to produce one big sorted list the examples here I also will will draw poles of a certain height so that you want to get them sorted in terms of their height uh we say run for assorted sub list so a segment of the array that's in order if you just look at this segment that's what we call a run in this context so merging gets two sorted runs and uh produces an output we'll always assume that we do this from the input into some buffer output area that just makes merging a lot easier so how does it work you start with the smallest two of the sword it runs because the the smallest in the result will either be the smallest of the first or the smallest of the second run all the other elements are bigger so we compare these two take the smaller one obviously the left one and then

1:41 Merging sorted lists

2:51 that's moved to the output and now we have a new smaller element in one run the other one's unchanged and we keep repeating the same game so we compare these two still this one wins so that one moves to the output and we continue next time this run wins and so uh speeding up the process a bit

3:18 um at some point you run out of run the first runs depleted and so from now on you don't really have to compare much more you can just copy over the remaining ones from the other run and then you have produced the sorted sorted output I guess those of you who answered correctly on slider will have seen something like this and maybe even code for something like this um

3:41 Clicker Question

3:47 let's see if you remember this as well uh I can find the question I was slowing blocking to show the results but a predominantly you've figured this out so

5:00 let me move on the correct answer will be Theta of n log n and so apart from the merge codes merge sword itself is is really really short um you could write it down with very little code so I just did this here again practice a little bit of pseudocode um it's a recursive procedure so we call ourselves here for the left and the right part

5:05 Mergesort

5:34 um yeah I'm passing a race around here so I don't know if we've had this issue before when I write something like this in in my pseudo code I'm assuming that we pass a pointer to the array and not copy the entire array that would be very slow and this is also so python would do it like that if you pass a list it's really passing a pointer to the list if you pass anything in Python it really passes a pointer to the anything

6:05 right so this is a recursive procedure you would also need some maybe some other procedure like sort which is given some array um and then you would need to call merge sort once

6:31 where now uh you know the parameters are zero and n or the the entire array uh that's for all of the recursive methods that we'll see here um they assume that you're sorting some slice some part of the array from some left to some right boundary and you need an initial call for the entire array on top of that um I will often leave that out on the slides to save space but uh you're you're of course right uh we need such a top level call then we determine the size if we're already done because we just have a single element we don't do anything otherwise we find the middle the middle gives us the left and right halves let me merge those assuming that we have some buffer so we have a second array that we can merge things into and then we copy copy the contents of the buffer back to our array all right foreign

7:41 let me show the analysis briefly and we'll I'll recap it on Monday in a bit more detail because I think it's it's not really proper enough time to do it now but to conclude the the section we can do it what I'm what I'm counting here is the number of array accesses and so uh if you if you merge you read every element once from its run and you write it once to the buffer so I count this as as two excesses once read one's right for every element so uh by and large we need two n array accesses for merging something that as the output has size n okay

8:34 um so okay I called it element visits but you can say array accesses so that's for one one merging round the cost is 2N well the entire merge sort you have a recursive description of the cost uh that's again something you'll um you'll practice where you have practiced this in tutorials in the context of inductive proofs and maybe that explains why you've gone through that well we will go through it this week and remember it was first or second tutorial uh but what this is supposed to say the cost for sorting a list of size n is defined in terms of the same function but for smaller uh values if we have just a single element then that the cost is zero we don't have to do anything but other than that we need to do merge at the end because the costs us 2N and we need to sort the left and the right half and so the parameters of these recursive calls to the to this mathematical function here about the sizes of the of the left and the right part and so we round down round up because n could be odd okay now this recurrence is nasty to solve because of the rounding up and rounding down it's really tough to get a precise

9:55 statement not undoable though but for us we will make our life easier by assuming that the size is a power of two and then the rounding goes away and instead actually these two become the same so we just get a 2 times that and that that recurrence is easy to tell easy to guess what the right answer would be in this this explains a bit how you arrive at that um let's do that on Monday