Video 3-1: §3.1 Mergesort

0:02 let's start with algorithms because these are often easier to uh to grasp and and to understand and I'll probably go relatively quickly through this as it's repetition for many but I want to give you a chance to show me how much you remember or how much you know if you haven't seen

0:29 it there's many questions coming today it's one of those topics where I don't have a good feeling for how much you know so I'll keep asking you so you'll have to tap a few more times let's try to do this one

1:07 and again if you don't know yet I'll tell you how it works it's just the speed at which I tell you will be a bit dependent on this um if you haven't seen it the same red book I should have brought my copy uh the red algorithms book setri and Wayne that is linked on unit two is also covering all that we uh do in this first part so if you want to read up the things at a reasonable pace for doing it the first time that's a good source right uh so most people uh let me let me give this away so most people uh get the second one we'll talk about the first one too um and then there's a few with uh don't know which again um that's fine you might want may want to uh read up on it in in a little more in a calm moment

2:07 so let's do a a quick a quick rundown of merge sort on the conceptual level I won't show you full code for the merging part um but that's again uh done in the algorithms book by sing veins uh in in full detail conceptually what merching does is you have two parts that are sorted so these triangles just should mean elements increase in in value they are already ordered so imagine this is your array left to right is the indices and the height is the value at that position Suppose there are numbers uh again the algorithms all just just work for any type of objects as long as you can compare them if I give you two you can tell me which smaller that's all we need but to make the examples easier to grasp I will often use numbers or Heights of bars so the conceptual VI of merging is you have two sorted Parts there they're sorted within but you don't know how they relate and you produce one big output that contains all the elements from the two parts and is entirely sorted how does this look like in an example here are two runs again Elements by height height is what we compare and you see they are sorted these just go up

3:21 and merging just can proceed like this these are sorted runs so the smallest element in each of the runs must be the first one that's the one where these arrows point to so we have two candidates for the overall smallest element and we just take the smaller of the two that must be the smallest overall in this case it's that guy and then we can just move that to the output so we we copy the element to um a result space so that will be extra memory as a buffer that we use in merging once that element is gone there's another first element in that room run so we again have to ask is this one smaller or this one by comparing them and again the first run is is the one that wins so we write that to the output and we keep going like this so in this time again we compare the first of the remaining elements of the runs this times this is smaller move it to the output uh and so

4:26 on and uh sometimes you can take a shortcut if you've completely exhausted one of the runs the rest you can just copy over because there's nothing else to compare them

4:40 to uh and that's that's basically merging now that's not sorting yet we already needed two sorted Parts but we could produce from two sorted Parts one big sorted part that's what we've what we've done so

5:02 far uh before we move on let's uh again probe your memories or your general knowledge uh where is my so let me point out this is asking for merge sort the entire thing not just merging what I showed you the example

5:58 for all right looks like a very clear picture so let me just give this away uh okay I didn't maybe I scroll down if uh there were more answers that's an absurd amount of possibilities I just put everything in that might remotely make sense um nlock n is the answer I I kind of gave that away maybe by saying that sorting has this complexity but it's good to remember so hammer it in a few more times doesn't hurt how do we turn this merging procedure into a sorting algorithm uh the abstracts um the abstract explanation is what popped up in the slider question you uh recursively sort the left half you recursively sort the right half then you have two sorted parts and then you merge those and uh the beauty of recursive algorithms is that that's all you really need to think about and that's what this algorithm does so merge story is is given some range of the array and uh the first call will will then be merged sort with the entire array so starting at zero ending at n if that's our length that would be the initial call um then uh we determine if we're already done if we have an if if we have a list of just a single element nothing

7:25 needs to be done because that's sorted in itself otherwise we find the middle point so if that is our array from L to R exclusive then we find this this midpoint M uh and uh we recursively sort the part up and up until m in excluding M and the right part from M onwards and then call the merge procedure that I showed you by example now that merge procedure needs an output buffer it doesn't work directly in the array that we're given and uh doing that is is actually possible but very tricky so you can you can do that but it's slow and so it's it's not very interesting uh the fast merging methods use some buffer area to write the elements too um and then here we copy them back so that we have this this outward outward facing interface of sorting in place okay that's all the code there is for it and it's not hard to implement that in your favorite language and I'll leave that to you you can see it in Java in the in the algorithms book I'm sure there's an easy python implementation to be found on the web uh what I want to briefly talk about is the analysis why is this n log n overall running

8:52 time um slightly differently from what some other books would do uh what I want to count here is the number of element visits and so an element is visited whenever it is it is read or written to an array now that's very related to the number of comparisons if you if you think about the merging procedure you read through one run you read through the second run in interleaf ways and you write the output once so the cost for a merge when you have two runs of length n uh sorry now if the output is of length n um then the cost of a merge is two times n and that's true even that's true in the best case and in the worst case it doesn't matter how the elements look like they always have to be touched read and written if you count the number of comparisons instead uh you get something that's between n and 2N so maybe worth writing down but um the anal is then we'll continue with this element visits as the elementary

10:21 between between and half I guess at least our merge procedure it would check is the first runs first element smaller yes yes yes if the first run always wins you explete the first run entirely that needs roughly and half comparison the length of the smaller run and the second run doesn't need any comparison it's just copied over so this is still roughly uh or upper bound is n uh but the math is a bit nicer if you do uh the element visits so you you've looked in the tutorials at recursive ways to express a function or a sequence of number numbers and that's what we'll do here for the analysis we say C of n is the total number of element visits to sort an input of size n and uh if the list is is short it's just a single element we don't actually touch that element we just return right away so that costs us nothing otherwise we do these two recursive calls and if you work out how long they are one is n half rounded down and the other is n half round it up that's the cost so we use the same function so that's the cost for recursively calling us on left and right part and then we add 2 N for the merging

11:40 that's where this recurrence comes from the second step is is a pure math exercise and you've done it a little bit in the tutorials for a simpler example um here one thing you can do is if you simplify by saying n has to be a power of two I'm only solving the recurrents for for a power of two uh then those two parts the rounding always works out evenly and you don't have to uh round then the recurrence simplifies to this um and you can actually spell out you can explicitly say what happens so you get the 2 * 2 to the K from the first from the first part from the merge at the very end of the algorithm then you have a first recursive call here and that gives you this green term in the next level down so you multiply it by two then you have 2 * 2 that's the 2^ squar uh but you go down in the argument by a factor two so that's why here instead of 2 to the K we only have 2 to the K minus one and if You observe what happens if you spell this out a few more steps you see that that's that's always the same thing you add a number of a power of two

12:56 in the front and you subtract a power of two two in the argument so all of these terms are actually the same because the powers just add up and so it has a nice closed form if you reinsert if you solve this for k then you get K is log n and inserting that gives you uh this this solution of two times n log n strictly speaking that's only true for powers of two right so um if you want a strict upper bound formally proven you could say this function this monoto and it costs more to sort a longer list so you can bounce C of n by making n artificially larger you're going to the next Power of Two And so you get an upper bound which is a factor of two away but it's still n log n now just because uh it's so cool and I want you want you to know uh you can actually solve this recurrence exactly it doesn't at all look like it because of these weird we rounding ups and downs it feels like that's complete chaos um but no you can you can handle the chaos and you get this precise solution it's an it's an equality no no approximation uh where you uh you have

14:15 the basic term that we found as well the 2 N log n shows up as the main term but then you have a a term 2 * n multiplied with something that's uh I guess it's between zero and one and it fluctuates depending on how close nend is to a power of two okay that's just a piece of trivia H treat it as the the fun fun bit of that uh slide and you can otherwise ignore it but that's merge sort um and its analysis where uh we've used recursion to uh write the algorithm and to write the

15:11 analysis so uh knowing already that this will be the optimal time complexity what speaks for merge sord is that even in the worst case it has this n logn uh up um complexity or upper Bound for its cost uh it happens to be a stable sorting method that's something we haven't talked about uh it's still true stable means if you have elements that compare equal so A and B A is less or equal B and B is less or equal a which you could say A and B are equal um that can happen even though the things are not identical so for example you could have a a list of people sorted by AG but they could be born on the same day or say same year or whatever but not be the same person right so a stable sorting algorithm would keep objects that are identical according to the Sorting Criterion in the order they've been in the input and that's um useful if you sort complicated objects like people several times so you could sort a list of people first by their first name and then sort that list by the last name if you do that with a stable method you will get a list that's sorted by last name and among those with the same last

16:30 name by first name and that can be useful if you do that with an unstable method if you sort by the last name of the second round it might scramble the order of the first names

16:49 again so merch sord is easy to make stable by when you do the two runs and there's a tie there's the two first elements that are equal you just take the one from the left run and give that precedence then uh you're stable so that's good for merge sword uh another thing this is uh getting a bit more technical we talked about our model for computers we said okay all we do is on the RAM on this on the word Ram abstraction of a computer now of course we still have to eventually use the computers we can actually build uh and they are not precisely that model in particular they have caches and a memory hierarch key and so um if you care about the performance in practice um it's another benefit of uh of merge sort that it uses it uses memory in a sequential way basically scanning left to right jumping one step at a time instead of randomly jumping around and that just happens to be faster because of caches that's not really something you need to know deeply for this module but I I thought it's useful to throw out um now merge sord has a a one big downside which is that it needs this buffer space for merging remember when

18:05 we take the two runs the only easy way to do merging and stable is to write elements to a buffer array uh and that means we need extra space I mentioned this before there are ways to work around this but there are mostly theoretical Curiosities not so much relev in practice so there's uh as a puzzle you can do merging in place and stable with complicated recursive tricks but it it ends up writing the data many times so it uh it comes at a prohibitive cost but it's