2.7.2. Merge Sort Algorithm

now we have seen what is merging and also we have seen how multiple lists can merge together that is in two-way merging or my merging we have seen and if there are multiple lists then we can merge them in different patterns we have seen that now let us see merge sort that is a recursive procedure and this is divide and conquer procedure the divide and conquer strategy says that if a problem is large then big the problem into subproblems and into problem becomes small then solve it and combine the solutions of the small problems or subproblems to get the solution for main problem so here the problem is to sort these elements and we say that the list is very large then what is small so basically if there is a single element then we say it's small so single element means we don't have to sort it so yes it more sort we saved it's just a single element then we don't have to sort this otherwise if there are two elements also we have to call it as a bigger problem or large problem if the single element and we say it's a small problem merge sort follows divide and conquer their force is a recursive algorithm let me write del Gordon let me write the algorithm then I will trace the algorithm let us see algorithm merge sort what are the parameters it takes it takes two parameters that is beginning of a list and ending off a list so low and high then we check if low is less than high means if low is equal to high it means there is a single element lowest less than high means at least there are two elements so list is large if flow is less than high then we will find out middle that is low plus high by two what for we are finding matter like if I find 1 plus 8 by 2 that is 9 by 2 I get 4 so this will be made what for we say that this problem is large so we break it into two sub problems and that's what we find mid then what to do with the left hand side perform a sort recursively perform a sort on the right hand side recursively so perform made final mid and perform merge sort from low to mid and also perform merge sort from mid plus one - hi so by performing one sort on the left hand side we will sort this one and we sort the right hand side so when two lists are sorted we are breaking this into two lists and when they were sorted we can merge them together so perform merge merge from there low-to-mid is one list and mid plus one too high so we passed three parameters so that's all this is a simple algorithm form a short this is a divide and conquer how merging is done we have already seen the procedure how marching is done but the point here is when the singularity is given for sorting we are breaking into two sub arrays and we are saying this is one fast list and that a second list so single array will be containing two lists and we have to merge them so cannot singularly have more than one list yes a single array can have many number of lists let us see how it works let us see the tracing now based on this algorithm only I will do tracing initially we will be passing low as one and high as eight so let us take for these set of elements so first time we will pass one and eight it will find out mid and it will divide the list and this side that side so mid is for form and perform a sort from low to mid that is from one to four it will go to the side and it has to go on the right hand side also but not now it will go afterwards but I will draw this one also so let us take this one so it will call itself from five to eight on the right hand side so it has broken them into two lists first part and the second part and then afterwards much so first of all let us finish this and this now most sort calls itself low is less than high yes one is less than four so again find out mid and call these two so it means this four elements are also large divide them so this side 1 to 2 and this side 3 to 4 now when we take this again lower is less than high yes there are two elements so this is still large again splitted so one to one on this side and two to two on this side now there are just one one elements see if you have seen previous video you may know how do emerge works - mr saw works see if you have seen previous video you know how to Weimer sort works now here also Mossad is working in a similar way when one array was given so it has splitted and then splitted then splitted now it has reached one one element now one element is diamonds is a single list with one element now these two can be mashed together three and nine are much together so the first merging is done for these two elements and their result is obtained here so this is the first emerging diamond this is the first much done it will more see these two elements so 3 & 9 are much then coming to this side it will split them and get 3 3 on this side and 4 4 on this side then it will merge the elements 3 & 4 are merged so first 9 and 3 very much so the result was 3 9 and now 5 m 7 & 5 are much result is 5 & 7 this is combined no it will go back and perform merge here so this is the third merge so it will merge these 2 so the result is 3 5 7 9 now this side is sorted actually we have to sort this whole array break it and break it and break it now to elements March 2 elements much no much needs to also so this side is sorted now same thing is done on the right-hand side also 5 to 8 is there so on that side it will divide this from 5 to 6 and that side it will be 7 to 8 and 5 to 6 will become 5 comma 5 & 6 comma 6 now 1 1 element each this is again spitted 1 1 element so these 2 are merged so it becomes 4 6 so this is the fourth merging then it will go this site it will split again 7-7 this side and 8/8 on this side so it will spin this also then again these two are much so it becomes to wait one molest so this is 50 merging now as these two are already sorted it will merge these two so it becomes 2 4 6 8 so this is 6 merging and then these two lists are masked to get a single list that is 2 3 4 5 6 7 8 9 this a single sorted list that is 7th Mon Shian so this is how my sort works when a single array is given recursively it will divide that array into smaller pieces until it reach one one element then it will start marching down so you can see that 8 elements were given splitted then splitted then splitted now they are much much much so this is the working of Masad all right so similar to two way but in two way merge sort we just take first two element the next to the next two but this is divide and conquer and this is recursive so it will simply divide and divide and then that saw it reaches one one element then it will start merging them so what is different is only the pattern is changing the approach rest of the things are same right result is sorted and it is also merging two lists at a time so it is also two way but as it is recursive we need some another name so we call it as more sort let us see the time taken by mass sort so from the tree dot recursion tree that is the tracing of that algorithm I have done so I will show you how the times how I will show you how much time it takes see the merging has started in this level this was just splitting so how many elements are moisture to two elements most two elements to Williams total how many elements eight elements are there two four six eight eight elements are moist here so I will say n elements are much all n elements then again merging is done at this level so eight elements are much then again eight elements are moisture so n elements are merged each time so total how many levels are there one two three or one two three so total three levels are there so for eight elements I got three levels it means it is log of eight log of 8 1 and then 2 then 4 so when something is raising by 2 every time and this power of 2 lastly power of 2 that is 3 at the last we are having one eight elements total so 3 is log of 8 so how many passes are there so actually these are not passes because it is recursive first it will enter this side then it will go that side so it is not passes all right first it will finish left side and right side but levels if you see so total how many levels login levels are there so this will be n how many times log n times so the time taken by mana sword is Theta off and login that's it so the time for this one is also unloaded now taking these numbers I will show you how this must sort works low and high are taken so example is 1 & 8 1 & 8 so let us see using the numbers I will show you first of all it will find out mid and it will call more sort on the left hand side so it will take these numbers and call 9-3 7 5 most sort is call on this then now this is 1 2 4 1 2 4 & this becomes 1 2 4 so this is the first call right first call then one to fall the first recursive call 1 2 4 s 1 is less than 4 so again it will call itself by finding men it will call itself so again it will split so this is 9 & 3 so just 1 & 2 1 & 2 then again this is also low is less than high this is low and this is high just you can follow that one find out mid and split it so 9 on this side this is just 1 comma 1 & 3 on this side just it is 2 comma 2 right so it has called itself and itself on itself again so this is 1 list it has splitted then again this is splitted again this is splitted on this side now these two are more so the result become what 3 9 right then it will go on the right hand side so this becomes 7 5 that is 3 4 then it will come on the left hand side this is just 7 3 then it is just 5 so these two are Maj so it becomes 5 & 7 second call has finished now this side is completed this side is completed so what is the next step March so these two are merge so this becomes what first 3 then 5 then 7 then 9 so that's how it has splitted then splitted then splitted then merged so till here it got that result now it will go onto the right hand side so this part second part for this one so this will be 6 4 8 2 and this is from 5 to 8 this one now on this side 5 to 8 on this one it is called 5 is less than 8 yes again find out mid and call most sort this one so on the left hand side it will be called so this become six four it will be five six in this is our five six then on this again one sort is called so 5 is less than six so again Fineman and calmer sort so it will become six and this is index five now low is also 6 highs also six it will come on the right hand side this call for this one so this will be 4 and the index is 6 so low is also 6 high is also 6 then merge these 2 are March so it becomes 4 first sorry then it becomes 4 first then 6 then it will go on the right hand side of this one so right hand side is 8 and 2 this is index 7 & 8 now low is 7 high is 8 so low is less again find out mid and call this one so this side it will be 8 and it will be 7 now just one element so go at the right side 2 single element now merge so left side complete at right side completed not much so 2 8 and B comes to 8 now this side decide both are sorted merge both are sorted then merge so this becomes 2 4 6 8 so this becomes 2 4 6 8 now this is also sorted this was already sorted before hand left hand side it went now these two are Maj together 2 3 4 5 6 7 8 9 so in this way this list becomes 2 3 4 5 6 7 8 9 sorted there's almost sort works tracing I have done see earlier I have shown just indices now in this I am showing numbers and as it is calling itself to tie the tracing tree will be more like a binary tree it will be like a binary tree and if I say the traversal then in which traversal merging is done post order first left left left then right then Ruth Marsh right then right left then right then root merge root March so merging is done in post order traversal that's it so I have shown you tracing in two different ways now let us find out the time complexity of this algorithm by using recurrence relation for this recursive algorithm let us prepare a recurrence relation and find out the time complexity of most sort if I say this algorithm takes T n time then this is one condition and this if I ignore condition and I say this is calculating mid then it is calling itself so T of what half of the list low to mid half of the list Rho n by two and again calling itself so this is also n by 2 then it is merging merging from where low to high two lists are there low to mid mid plus one too high to list total n elements so merging takes end so if I prepare recurrence relation by adding all these ignore one there now this is T and is equals to two times T and Y 2 plus n so the recurrence relation is T and s equals to 2 T n by 2 plus n when n is greater than 1 what it is doing when n is equals to 1 it's not doing anything so we don't write 0 we can write 1 or some constant okay some constant means 1 then anything you write it's not doing anything so better write 1 this is the recurrence relation now by using master's theorem a values to be values how much to an fo fanna SWAT and now find out Lord a base B so that is log to base to s1 and power of n K it is one so this is log to base 2 is equal to K they are equal so we compare these two and this is falling in case to case 2 so case 2 says what whatever F of n is multiplied by log n right F of n as it is and multiply it by log n so I am using master theorem already this recurrence relation is solved in another video you can look for that video right it is in the second topic that is divided conquer I have solved few recurrence relation this you will find in the title of a video itself now here are directly I am using masters theorem these are videos on master theorems also so time is teat of n log N

Channel: Abdul Bari

Views: 809,589

Rating: 4.8868637 out of 5

Keywords: algorithm, algorithms, mergesort, merge sort, recursive merge sort, recursive mergesort, analysis of mergesort, drawbacks of mrgesort, abdul bari, bari, gate

Id: mB5HXBb_HY8

Length: 20min 23sec (1223 seconds)

Published: Wed Jan 31 2018