Video 3-2: §3.1 Mergesort

0:00 <Untitled Chapter 1>

0:05 let's briefly leave the world of theory and have a look at one concrete sorting algorithm that you probably know uh but i'll go through it briefly and from scratch but yeah maybe we can check first where we are so here's a quick question on on merge sort

0:12 Clicker Question

0:27 i'm hoping to get this get this one done quickly uh the question was if merge sword is the fastest uh merch so if merch of the fastest sorting algorithm the answer to that is quite complicated because it depends on what exactly you are asking well we'll come back to this most of the unit is actually about something like this question

1:28 yeah there's many facets to this question um worst case versus average is one of them uh we'll touch on a few more actually all four answers apart from the don't know are actual sorting algorithms and they're all kind of reasonable but only one is merge sort shall we jump to this

2:00 right so two-thirds or so of you know this but i could trick some of you into answer a which is another really good sorting algorithm but we'll come to that later so the essence of merge sword is is the second answer but i'll um i'll explain it in in detail anyways let's start with the core step in merge sort which is merging um pictographically you have two sorted lists so sublists that are already in order and we would like to make one big list that is containing the same elements and is entirely sorted that's what i what i mean by this this picture and let's just look at an example how this works so i'm i'm showing elements here by the height of the bars and well the height is what we compare i haven't changed thanks

3:04 Merging sorted lists

3:05 i have to look at the monitor more often the key step in merge sort is merging and here's the picture that i wanted you to see and you couldn't see so you take two parts that are sorted within but there's no relation between an element here say and the element here we don't know how they compare yet and we want to produce one big sorted output like this

3:35 uh and here's a tiny example for that and again the elements are shown just by the height so how do we do this um we start with the smallest two elements and we compare them in this case the one from the first run is smaller so we put that one into an output buffer so first thing to note merging is is easy to do if you have extra space to hold elements it's more tricky to do if you don't have that it's not impossible though but we won't we won't use that and it's not really practical either

4:11 so we put the smallest element to the output and then we continue we update the first pointer in the runs this one's still the first in that run and here we move to the next one and again from run one this is smaller so we take this guy and move it to the output and then you see how this continues right you always take the smaller of the two first runs that's remaining in the in the two input runs and put that to the output and at some point it can happen that you've completely depleted one run then for the other ones you can just copy them there's no need to do further comparisons okay that's merging

4:53 i'm not sure if i spell that i don't think i have spelled out code on the slides but i guess most of you would be able to code this in python or some other language if you're given two lists and you produce this output list

5:10 all right let's see what you know about merge sword now that we've seen um how merging works and you've seen at least in the slider question how merge that is defined

5:29 so just as a recap we've seen merging now merge sort recursively sorts the left half then the right half then we have two sorted lists which we can merge to get the final result okay there's many many answer options

5:56 30 we had something like 51 53 everyone can have a vote on this i think so yeah it says worst case which is kind of it well might be important

6:22 okay everyone voted i think same number oh more people this time brilliant uh good there you go um somewhere down the line here's yeah and login and i switch back first before i move over here so we'll we'll have a look at why this is the case so if you haven't seen this and you just guessed something don't worry

6:51 but we discussed n log n in terms of sorting so maybe it was it was even possible to guess um here's concrete code for merge sort using merging as a subroutine uh not sure if it um needs much explanation uh one thing i want to say is here uh when i when i pass an array i write this as a and then boundaries first of all this notation it appeared earlier on the rules of the game slide but i didn't point it out so the last left endpoint is usually inclusive which i denote with this square brackets and then the right endpoint is exclusive so it points to one element behind the last if you wonder why on earth one would want to do this it's often a convenient convention for example you get the length by just taking the difference you can call the recursive calls with the same parameter for endpoint of the right of the left run and and starting point of the second run it's the convention followed by most languages too especially those that work with iterators or pointers so the way to think about this here if you pass the array into this function it is not copied instead we we copy a pointer to the list and actually two pointers one to the

8:14 beginning and one to the end or you copy a pointer and two indices um so uh you have to be careful if you in python write this like that it would actually be a copy so don't do that instead you have to pass the list without a range then it's a reference and you pass to indices just in case you feel like coding this up in python yeah so we split in the middle that's our m then we sort left and half right half and merge that and my merging method here has an output buffer like the one on the slide and so the last step is to copy the buffer back to have have it in the same array okay

9:01 we call this approach a divide and conquer approach because it divides the problem into sub problems and then conquers them by combining the results we need temporary storage for the result otherwise things get really tricky uh yeah one thing to note from from the example before when we merge two runs what we do in terms of uh dominant operations i want to count here um how often we read or write an element that's a good proxy for running time apart from comparisons uh so you at the end of the day you will have read all the elements in the two runs once at least and you can buffer them in between and you will write them out to the output ones so a merge costs two times as much as the size of the output is because you have to read everything once and then write everything once okay think of it if you want in terms of cache misses or memory transfers that's the expensive operation here

10:10 now we can precisely analyze the number of these element visits so a read or write using um a recursive uh sequence that's something you will i think you do this in the tutorials this week so you will see another example of this type today and tomorrow

10:33 the way this works is you say the total cost for merge sort is c of n and now if the list is is essentially a single element or empty that costs me nothing i don't have to touch it and otherwise i have to do these recursive calls so i'm calling myself after same cost but on a list of half the size and if you want to be precise you have to round up and down and i have 2n that's the cost for the merge as i just explained 2 times the size of the output that's the number of accesses that we need for merging all right and as you pointed out this is the same for the best and the worst case for the number of comparisons there's a slight difference because the best case is that you don't happen to compare you don't have to compare all the elements because one run was completely empty and then you could copy over things but this it's not a big difference a factor of 2 or something but for this convenient measure element visits worst and best case are the same this recurrence is still tricky to solve but if we make the simplification that we only look at inputs of us whose size the power of 2 then you can

11:45 easily solve it because then all these roundings go away so instead of n we have 2 to the k instead of n half rounded down we have two to the k minus one and this one is also because it's it's never rounded it's always an integer if you have a power of two so we just have two times the same term and then here again an n gets uh up to the decay and if you look at this recurrence uh that just nicely telescopes in the sense that you can you can write this out the first term you get from this general one is just this one first for merging and then we have two times inserting what is here so um

12:31 you have the the factor two from the front from here times the two from here that's two to the two and the k is one smaller inside the recursive call that's why it's times two to the k minus one it's unfolding the recursion and if you keep doing this you notice actually all those sumans are the same because uh the exponents just add up and so this is always summing to the k plus one and you can write this as two times to the k and we have k of these sumans

13:20 so we have an exact solution for this recurrence when we substitute the size as a power of 2. it's exactly this and if you substitute back if n is a power of 2 then

13:39 n is a power of 2 then that means k is log n so if you substitute that back in you get the solution down there um and maybe you can try to keep in mind the two times n log n as the precise answer of course that is in in theta of n log n if you want to ignore the constants but when inserting you don't really want to ignore the constants because it's it's so fast you you feel the constant factors

14:23 you may have seen this recurrence written with comparisons but i want to stress one more time that element visits is a slightly more realistic cost measure if the list is not too small

14:37 Mergesort - Discussion

14:40 so what can we say about merge sort we can say a lot of good things it has the best possible running time of of theta and log n we'll see why this is best possible later but you can you can believe it or take it take my word for it for now it has the feature that the sorting is stable so uh that's often useful um it means if there's elements that compare equal according to your your lesser equal function then they remain in the same order they have been in the original input why is that relevant the typical example is think of an excel sheet and you have first name last name and you want to sort and many other columns maybe you want to sort the excel sheet according to last name but among the people with the same last name according to first name alphabetically so one way to do this with a stable sorting method is first sorted by first names and then by last names and so all the people with the same last name will compare equal in the second sort but because they were sorted by first name previously they are still sorted by first name after that but that's only true if the method that you use for sorting is stable

15:51 if the method is not stable the second sword might mess around the order that you established in the first run and then you would have to do some more complicated comparison functions say that you sort in one go the list and compare the last name unless it's equal then you compare the first name and that's if you sort in excel you can specify several columns but under the hood it's faster to do it with two runs of uh of a stable sorting method often

16:26 uh another thing so this is um if you know a bit about computer hardware computers have caches and they have several hierarchies of caches indeed so what they really like is sequential access where you run through an array one one step at a time and what they don't like is jumping around wildly and by don't like i mean it costs time because the jumping around means you have to get a cache blog each time whereas sequential means you get a whole chunk of memory into your cache and then you can use all the positions in there before you have to load another block and yeah the accesses in in merge sort are all sequential scans so that's good in terms of the memory hierarchy if that didn't make sense at all to you uh it's not really relevant for this module it's just background information that uh is very relevant in the world out there if you think beyond the exam for com five to six there's a negative side i said this for merge merging is easy if you have extra space and if you don't it's not entirely impossible but very complicated and you lose the practicality to to a good extent so we have some work to do if you want to sort without spending as much space

17:41 as already the elements take