Video 3-2: §3.1 Mergesort

0:00 Intro

0:02 in the next subsection i want to present merge sort one of the two main sorting algorithms classic sorting algorithms that we will discuss and also one off of the practical ones that is used um a lot for for practical applications that require sorting

0:22 Question

0:25 before we start i want to ask you how much you know about this so that i know uh how fast i can go with this so here's a couple of of different more or less sensible ways how you might approach sorting and one of them is merge sort so please let me know which uni you think is is the right one

0:47 and um [Music] yeah i probably should let's wait a little bit and then move on but uh if if possible let's try to keep this oh okay i am i'm aware that not everyone um got a chance to vote up to now but let me show the results either way there's quite a few people who say they don't remember so i'll present that and the majority has has the right idea in mind um exactly that is what what merge sword is about um so let's uh let's see how that looks um merging merge sword works by merging sordid lists that's in the name i guess um and so how i want to pictorially represent this like that so you have to sub-lists you have two parts that internally are sorted ascendingly but there's no we don't know how they relate not in this in this picture and what we produce out of this is one big sorted list so

2:37 how are we doing this suppose we start with two two runs like this so they are these these sorted parts it's just four elements to keep the example small but of course it works for arbitrarily many uh elements and here is the output area where we show where we collect the the result in sorted order how does merging work you start at the beginning of each of the sorted runs and you compare these two elements and the smaller of these has to be the smallest element in the entire collection because they're all sorted all of these guys are taller than this all of these guys are taller than these and that one's the smaller of those two so that is the global minimum which means we can safely put it as the first element into the output

3:38 and then we continue doing the same thing but now starting well with the first element that remains in these runs again we do the comparison that's the smaller one so we swap it over and we've we've grown the result by one more element we keep going this time the second run wins so that one goes to the end one more time uh one more time and at this stage we actually know uh the rest can just be copied over as it is because um the other run was completely exhausted so there was there was nothing um left to do here all right um that is merging now we built merge sort out of recursively doing this and before i show you the details um i want to know what you know about the running time of merge sort

4:43 Code

4:45 show the code for this so while you vote here's the the procedure for merge sort merge sort is given an array and some in general some range in that array initially we call it with one and n the entire array or well zero n minus one uh depends on your on your flavor

5:09 uh we compute the current size if it's only one element we stop that's the the recursive um base case and otherwise we split the list in half that's uh what the majority of you also said uh how much merchant works is sort left sort the the left half sort the right half and then merge them together i've shown you how the merging step goes very briefly just the previous slide but merge sort first recursively sorts the left half then the right half and then merges the two together writing the output into some temporary storage and then we have to copy the storage back so that it's at the end in the same array that we started with

5:59 this is also called a divide and conquer approach because you well you subdivide the problem and then the conquer part is to combine the results from those two recursive calls and we need some temporary storage to do the merging remember from from the example you always move the elements to this output area okay i see most of you have voted for this and indeed almost all of you know that merge sort has n log n performance um so that's good we can keep going with this

6:42 Analysis

6:46 um what i want to show you here is i think i have to turn myself off what i want to show you here is an analysis of merge sword that's a little more detailed than uh what many people present so i want to spend a minute on going through this slowly but it's also it's also very simple in elementary in a way we want to analyze how expensive is is this merge sort procedure and what i'll do is count the number of element visits that's essentially array accesses so we read or write an element from or to the array

7:30 and for that um sorry what i wanted was this i wanted to show my face in between what we will set up is the c of n is the cost to sort a list of size n and we will express the total cost of merge sort as a function of merge sort itself on smaller sub-lists that's exactly following the structure of the code so the analysis exactly reflects what the code does and translates it to a mathematical formula you will look at examples of how well you have looked at examples of how to solve such recursive recursively defined sequences in general it's fairly complicated in this case we will we will be able to do it with the trick i'll show that in a second in more detail and that's an effective way of analyzing recursive algorithms

8:34 so what is the cost of merge sort in terms of these number of element visits if we are in this case that n is less than one so we just return here we haven't really touched any of the elements so the cost is zero otherwise we split the list into two halves and look here we have to round down because uh n might be an odd number so what we have is um a first recursive call where we round down and divide it by two and a second where we round up and now the interesting part is is the plus 2n so maybe um just to make this super clear let's do color coding this is this recursive call um this is the second recursive call and the 2n comes from the merge where um maybe let me go back to this briefly if you remember what we did here in the merging procedures we we read every element on the left one time when we compared it to well we read it several times but we only really visit it once and then we move it over here each element is once the minimum of this comparison and then it's it's moved over there

10:04 so the 2n comes from the fact that we have to read both of the runs and then we have to write the output to the output area so that's a recursive formula for the cost of merge sort but this this formula by itself is not really telling us much

10:28 interestingly the same formula is true for the best and worst case merge sort in terms of the number of element visits doesn't really change its behavior depending on the input it does the same the same costs it uses the same cost in each case so this recursive formula doesn't really help us much so we have to make it more explicit and that seems in general challenging because of the rounding up and down but if we restrict ourselves to inputs that are powers of two where k is an integer

11:05 then we can simplify because then the rounding is never needed we can always in a power of 2 we can always divide by 2 and get an just another another integer and then those two are actually the same right this is uh we get it once for the blue and one for the red time and the recursive call on half the size is just instead of two decades to the k minus 1. and 2n uh this is a fancy way of writing 2n so that's another simple step and now here you notice that this is a telescoping recurrence

11:48 what i mean by that is if you insert again the recursive definition for this c insert that again you get the same thing um and you can keep inserting uh by doing this a couple of times you will spot the pattern and then you can prove the pattern correct in this case the pattern is um we get the two times to the k that's uh from the first round of merging and then we get two times the recursive thing but the recursive thing will give another green one so the the first recursive call here that has a factor of 2 times this with k minus 1.

12:33 and that's what you have here you have the cost with k minus 1 and a factor of 2 in front and if you look at it this is exactly the pattern that repeats you get a bigger power in front but you reduce the power of the cost for merging so that the product of these two things is always constantly two to the k plus one and uh how many times how many sumans do you have here exactly k that's a um this is k

13:13 identical sumans and each is 2 to the k plus 1 that's if you just combine those two well in that um remember when when n is 2 to the k that means k is log base 2 of n so if you insert n again here you obtain this final result that c of n is 2 times n log base 2 of n and that's theta of n log n if if you remember the rules we can ignore constants and we can ignore the constant base of the logarithm that was the analysis of merge sort showing not only that it's theta of n log and total running time but also if you count element visits how often do you have to well bring a certain element to your attention in a vague sense um you get a precise formula for um for inputs that are a power of two uh and that is that is this formula we'll we'll come back to that and compare it later with other sorting algorithms

14:25 Conclusion

14:28 uh to wrap up the discussion of merge swords let's briefly see how it how what it does well and where it can be improved what's good is that it has the optimal time for sorting well we'll we'll see that this is optimal up to now we know it has theta and log n cost even in the worst case and that will turn out to be a good running time it's also a stable sorting method which means um that's a a coin term in sorting if you have uh elements that have that compare equal with respect to the order that you're sorting then a stable sorting method keeps them in the same relative order that they had in the input that sounds a bit esoteric but it's very natural if you think about a spreadsheet application where you have different columns you might want to sort the entire table first by first by given name and then by last name if you do this with a stable sorting method the rows will at the end be sorted well by last name but among those people with the same last name they will be sorted by a first name by given name that's often something you want uh in in well several applications and merge sort is a method that is stable

15:59 it's also good that merge sort does sequential scans over its input that means it's possible to do it even on linked lists it also means it's friendly to caches and the memory hierarchy something we won't talk about in more detail but it turns out this it's much cheaper to sequentially scan an array compared to randomly jump around in it with random accesses the big downside of merge sort is that it needs extra space for storing the output now the fine print is you can implement merging in place using essentially only the the given array as your as your storage space but these are either not stable or they become very very complicated and even though there are implementations on the web you can you can google for stable merch or for for in-place merge sort um but they're yeah they're not competitive with uh the running time of good um well implemented other sorting methods um so it's uh the practical fast version of merge sword needs extra space and that is a downside of merge sort