7.7 Merge Sort Algorithm | Sorting Algorithms| Merge Sort in Data structure

so the topic is mergesort see we have already discussed quicksort so in quicksort the main idea was or you can say the backbone of that sorting technique is the partition method in merge sort the backbone of this technique is or the main front line this technique is merge processor okay so in this video I am going to discuss with you the working of this merge sort with help of an example and we are going to write down a piece of food for this sorting technique okay so this sorting techniques also works on divide and conquer technique as in quicksort technique fine now what is that technique in this case the complete area you can say the complete list is divided into sub lists fine or you can say the complete complete list is divided into n sub lists and each sub list is having one element or you can say will will keep on dividing the list into sub lists and till be cut and until we get the sub list having one element only fine after that we are going to merge the sub list and we will keep on merging the sub list fine to adjacent sub list you can say to produce a new sorted sub list and we'll keep on merging the sub list until big until we get one complete sub list and that sub list would be sorted sub list so the first step is dividing the given list into sub lists fine second step is merging of those sub lists to get a one complete sorted sub list sorry one complete sorted list so these are two steps main steps see let us take an example and see how this merge sort will work so let us take this example we are having this array array name is a we are having nine elements and these are the elements you are going to sort these elements in ascending order applying this merge sort so first step is we are going to divide this list or this array into two equal sub arrays fine equal sub arrays means you have to find out the position and you are going to divide this array from that mid position fine see how to find out a mid position 0 + 8 C 0 is lower bound this one is your upper bound is 0 + 8 is 8 8 divided by 2 that is 4 so 10 4 0 2 4 1 sublist is there like this you can write we are going to divide it into two sub lists 15 5 24 8 n 1 0 1 2 3 4 from 0 to 4 we are having 1 sub list and from 5 to 8 we are having another sub list 5 6 7 8 like this ok still this this sub list is having in how many elements five elements but we are going to divide the sub list till we get a sub list having one element so we are further going to divide the sub list okay into two halves 0 + 4 that is 4 4 divided by 2 that is 2 so my position is 2 from 0 to 2 15 5 + 24 this is 1 sub list and another sub list would be 8 + 1 from 0 1 2 here we have 3 to 4 right this will be again divided into two parts and 3 16 would be in one sub array and this 10 + 20 would be in another sub array fine again this list would be divided in two parts middle middle is 1 0 plus 2 is 2 2 divided by 2 that is 1 so 15 and 5 this would be in one list and this 24 would be in another list same this would be divided into two halves fine and this would be 8 and this would be one sub list will be having one element this would also be divided into two halves one is having one element three one is having one element sixteen here one is having element 10 and 1 is having element 20 now this one is having element 15 another is having element five fine now we cannot further divide these sub lists why so because each sub list is having only one element and that is the condition you have to stop dividing you will keep on dividing the sub list until you until each sub list is having only one element now each sub list is having only one element now next second step was you have to merge these sub lists so now till now this divide the first step is over now second step is is what for merging okay now if I write down the algorithm then how we will write C merge sort we are going to take a function merge suit is array we are going to pass lower bound and upper bound this is lower bound and this one is upper bound right and if lower bound is less than upper bound it means at least that array is having two element lower bound is less than upper bound if two elements are there if two elements are then then you are going to divide that particular list into sub lists okay and then each each sub list is having only one element so now if this condition is true now next is we are going to divide the array into two halves equal halves so for that thing you have to calculate mid element how to calculate mid element mid as equal to lower bound plus upper bound / - fine now we are again going to recursively call merge sort on array a and from lower bound to may see from lower bound zero to mid hair mid is what for because 0 + 8 0 + 8 divided by 2 that is 4 so mid is equal to 4 so 1 1 half is from 0 to mid and next half is from 5 to 8 that is mid plus 1 to upper bound so next is mergesort on array a from mid plus 1 to upper bound right and this is what recursive call we are going to recursively now again we are going to divide this into two halves from 0 to mid to mid plus 1 to this one again we are going to divide into two halves so this is a recursive call to left part n to right part fine finally after that we are going to merge these arrays fine so after this merge sort next next is what a method that is merged we are going to merge these arrays now in merge we are going to pass in a we are going to we are going to merge these two halves so from lower bound to mid 1/2 is from lower bound lower bound to mid and another is from mid plus 1 to upper bound so from mid plus 1 to upper bound so you are just going to pass these parameters lower bound mid and upper bound fine so this is the merge sort now here the main thing is you have to write down the code for this merge function that this backbone of this merge sort is this merge function how we are going to merge these Ares ok now if if you I this is the recursive code fine this is recursive call if you if you draw our recursion tree for this this numerical then how you will draw see first of all we are going to call merge sort suppose I am going to write mas only fine Eddie a I'm not going to pass away I'm going to pass this lower bound and upper bound lower bound is zero upper bound is it fine lower bound is less than upper bound yes that is true then you calculate made made is equal to zero plus a divided by two that is for fine again merge three statements are there this this and this so I'm going to divide into in this into three parts so here we have again merge sort merge sort I'm going to write a mess for my soul lower bound to mid lower bound is 0 mid is for fine again second is mergesort mid plus 1 that is 5 - upper bound is 8 and next is this merge would be merge would be lower bound is 0 mid is 4 and upper bound is 8 from 0 to 4 and 5 to 8 we are going to merge these arrays but after sorting of these sub arrays fine now from 0 to 4 again recursively merge so much so it would be called from 0 to 4 0 is less than 4 yes calculate mate mate is equal to 0 plus for the divide by 2 that is 2 midpoint is 2 now again call this merge sort now see M is 0 to 2 minutes - now here again M is 3 to 4 now here we have merge 0 then made is 2 then for 0 to 2 and + 3 to 4 we are going to merge these two halves now next is see this one from 0 to 2 0 is less than - yes calculate mid 0 plus 2 2 divided by 2 that is 1 min is 1 again for a merge sort zero two middles one merge sort zero mate is one then mid plus one - two - only one element we have now now here we have merging of zero to one and then to fine now here again 0 & 1 0 is less than 1 yes calculate midpoint midpoint is what 0 plus 1 divided by 2 that is 1 divided by 2 that is 0 0 is midpoint fine so here we call merge sort 0 - middle element is 0 because 0 plus 1 that is 1 1 divided by 2 is 0 and then again merge sort 1 to 1 and again we are going to call merge methadone 0 metal point is lower bound is 0 mate is also 0 and upper bound is 1 from 0 0 to 1 to 1 fine here we have 2 - that is one element is there only so we are not going to divide this anymore because lower bound is - upper bound is also - who is less than 2 no this condition is not true so we are not going to divide this this is worse now come to this point 3 is lower bound upper bound 3 is less than 4 yes then we are going to divide this into three parts see 3 is less than 4 yes find out midpoint 3 plus 4 that is 7 7 divided by 2 is 3 only fine so here we are going to call merge sort lower bound is 3 mid is also 3 second is merge sort 4 to 4 and this one is merged 3 3 & 4 fine 3 3 lower bound is 3 upper bound is 3 3 is less than 3 no 4 is less than food no we are not going to divide this merged this then again we have this merged then finally this one merge so 5 - 8 5 is less than 8 lower bound is less than 8 yes we are going to divide this one now now see calculate midpoint 8 plus 5 that is 13 13 divided by 2 that is 6 we have so middle point is 6 mergesort 5 to 6 then mergesort 7 to 8 and then we are having merge 5 6 & 8 then again come to records equal to this 1 5 2 6 5 is less than 6 yes again divide this one into 3 parts calculate a midpoint 6 plus 5 is 11 11 by divided by 2 is 5 so merge so 5 to 5 then merge sort 6 to upper bound is 6 then we are going to call merge 5 then 5 and then 6 fine lower bound is 5 mid is also 5 and upper bound is six now seven 8 7 is less than this it yes this condition is true to again divide this into three parts now I'm going to divide it here only so now first is mergesort 7 plus 8 calculate midpoint 7 plus 8 is 15 divided by 2 is 7 so 7 is midpoint 7 to 7 then merge sort mid plus 1 8 to 8 and then we are going to merge 7 7 8 he and finally merge 5 6 again finally merge 0 4 & 8 so this is the recursive tree now how this is going to be called see first of all massive of 0 to 8 here we have first cold would we do this function 0 to 4 we are going to first of all call the merge sort on 0 to 4 again for first sorting of this one we are supposed to cool this one again we are going to hold this one 0 to 2 for sorting off from 0 to 2 we are going to divide this again so here we go from 0 one only now for sorting of zero then zero then one element we are going to divide this into two halves only if you so here we are going to call this one M is 0 0 and M is 1 and 1 0 0 means we are having only one element now 0 0 that is 15 here we have 15 and here we have only 5 because we cannot further divide it fine so this one is done this one is done now next step is now control would go to this merge now merging of 0 to 0 0 to 0 is 15 and 0 or you can say 0 to 0 then 1 to 1 1 to 1 is 5 then you are going to merge this 15 and 5 now how this merging is to be done see two sub lists are there which are already sorted you are going to merge those sub lists and you are going to produce a new sub list and that new sub list is also in sorted order fine so after merging of this 15 and 5 the new sub list would be 5 and 15 right how they are going to merge I am going to explain that processor also but for now you have to keep in mind that you two sorted sub lists are there you are going to merge those sorted sub lists so the new new produced sub list would be its sorted order so this would be 5 and 15 so after merging the list would be 5 and 15 5 and 15 done now now the control would go to here only ms 2 n 2 2 n 2 so this is only one element is there 2 into that is 24 fine now this one is done now 24 is there 24 is there now control will go to here only merge of 0 to 1 0 to 1 this list and this list is what 5 and 15 and from tu-tu-tu-tu-tu-tu is 24 so now we are going to merge this and this that is why I am saying you cannot merge this 15 with 8 or 15 with 24 but it's not like that if this 5 and 15 is 1 list and you are going to merge this with 8 no we are going to more we are going to merge these list with its adjacent lest only and when you are going to draw this recursive tree then you come to know that how we are going to merge these sub lists and how you are going to divide these sub lists fine now this sub list would be merged this and this now this list would be 5 15 and 24 5 15 and 24 now fine now now control would go to here only now this one is done 0 to 2 now list 0 to 2 ways what 5 15 and 24 the merging has been done now control would go to here only merge so 3 to 4 now again recursive cool so control would go to 3 to 3 1 element is there 3 3 that is 8 we are having 8 now control would go to here for and for one element is there that is 1 only now control would go to this much we are going to merge 3 2 3 3 2 3 methyl of 8 and then 4 to 4 that is 1 so we are going to merge these two and the result would be 1 & 8 fine so here we go toward 1 & 8 after merging I am going to discuss this merging method also now control would go to here only now this one is done now control would go to this merge now we are going to merge from 0 to 2 0 to 2 this one and 0 to 2 the list is this one we have got this list fine and from 3 to 4 3 to 4 the list is 1 & 8 now we are going to merge this 5 15 24 with 1 & 8 fine and after merging of this to now the list would be this one five eight fifteen and twenty four and this step you are going to find out this result because when you are to sort when you are merging two sorted sub lists then dessert the result would also be a sorted list fine now now this one is done now again we have done from zero to four now control would go to from five to eight now again the same processor would be there the control would go to recursive call is the other from five to six then from 5 to 5 then here six to six then merging would be done then again back to seven to eight then this one this one this one and then finally merging of these lists fine so here merging of these two then merge them of these two then finally this and this merging of these two fine and ultimately you will get one complete sorted list fine now I am going to discuss with you how this merge function is going to be executed now check we are going to merge first of all these two and how merging would be done two sub lists are there we are going to compare the first element of these sub lists fifteen and five which one is less five is less so we are going to put five first of all then we will put what 15 so this is the new produced sub list sorted sub list fine now this would be this would be merged with this 24 this 24 now the new sub list would be 515 in one sub list three or five and fifteen in one way or 24 now compare five for 24 which one is less five so we will put 5 here then 15 with 24 15 is less then we were going to put 24 this is the new sub list now now eight with this one and the new sub list would would be one and eight now this with this one and eight so finally the new sorted sub list would be see compare five with this one which one is less one one then here we have eight here we have five five with this eight five then eight then 15 then we have twenty four fine same here we have three and sixteen here after merging we will get ten and twenty after merging of these two what you will get three ten sixteen and then twenty now we have two halves one is this one and one is this one now finally you are going to merge these two and ultimately you will get what one list that would be sorted fine and then we will stop what merging fine now see now this sub list are there and this sub list is there now how merging is to be done let us see so now we are having two pointers one is suppose a pointer that will be pointed to this lower bound one is this J pointer and two sub lists are there one is this and one is this one maybe you can say this is left and this is right sub list another list is there we are going to produce another sub list sorted sub list find another pointer is there that is K which is at the starting of this sub list fine and how many elements would be there in the sub list total of this and this one let us suppose here we are having M element here we are having n elements so total would be what M plus n elements fine so this merging this merging function the time complexity for this merging function would be what theta M plus in M is number of elements in one sorted sub list and is number of elements in another sorted sub list when you are going to add these elements into this one then how many elements would be there in this key in this sub list M plus n so time complexity for this merge function would be theta M plus N fine now how merging is to be done first step is we are going to compare now first element of this with this but you can say suppose name is L this name is R so now we are going to compare L of I with L R of G and that which element of it element which is less we are going to put that element into this sub list fine so 1 & 3 which one is less 1 so we are going to put 1 here next step is we are going to increment this K now K is at this place and we have placed 1 here so now we are going to increment this I also now II's at this place now again compare L of I with our of J 5 and 3 which one is less 3 so we are we are going to put 3 here again we are increment this K and we are increment now this J because we have put this 3 here only fine now again compare L of i-5 with our of J that is 10 5 is less than 10 so we are going to put 5 here on increment K K is now at this place and increment I now now again compare it with this 10 it is less than 10 so we are going to put 8 in this new sub list now increment this k now k K's at this place and increment also I fine now again compare 15 with this 10 which one is less pen so we are going to put in in this sub list and increment this J now J's at this place and increment this ki now he is here now again compare 15 with this 16 is because here and J is here only 15 is less than 16 so we are going to put 15 here so now increment I and increment K 24 and 16 which one is less 16 so we are going to put 16 here now increment this.j and increment this K fine now 24 and 20 which one is less 20 so we are going to put 20 at this place now increment this K and if you increment this J now J is greater than this upper bound fine it means this list is now exhausted means you have put you have already put this element all the element of this sub list into the new list sorted sub list fine so this is now done now what you have to do now one element of this sub list is remaining now you simply simply put this element into the surplus 24 fine and we increment I so increment is also now greater than this element so this one is also done now if suppose here 25 is also there 30 is also there now what you will do now see this list is done now so you simply put all the remaining elements of this sub list into this one 24 25 and 30 like this fine here in this case we have only one element left over so we simply put 24 here on so this is now the sorted list fine after merging move these sub lists or this is if this is how the merging is to be done fine so now if you write down the code for this merging technique then how we will write see we are having function word merge fine array we are going to pass lower bound then we are going to pass mid and then upper bound fine now next is see we are going to take I J and K 3 variables and I is equal to from lower bound and J would be J would be from mid plus 1 because see here mid is what for so J is from here 5 so J would be from mid plus 1 and K would be is equal to from lower bound only from 0 only now next what you are going to check is you are going to write down a loop while this is less than equal to mid this i is less than equal to mid and plus this J value is less than equal to upper bound J less than equal to upper bound in that case only you are going to compare these elements and you are going to put the element which is lesser into this new array fine so now you compare if if a of a of IFC name of the series a a of I is less than and equal to a or J fine because the air is this array name is a only so a of I is less than equal to this a of J then what you will put you will put this a of I into this array so we are going to take another array that his name is B so B of K see we have taken one variable okay so B of K is equal to a of I fine and next what we have done I plus plus and K plus plus right else and suppose this a of I is not less than used a this this a of J is less than your file then what he will put you will put this value into here only so else what you will do in B of K you will put a oz j not a o file and then you will increment J plus plus and a plus plus fine so say in both the cases we have we have that what K plus plus and K plus plus so if you will not write here then you simply write here k plus plus you can no need to write here only you simply write out of this if and else you simply write k plus plus because in both the conditions you are going to do what k plus plus k plus 1 you can say fine so this is to be this this processor is going to repeat until we have I less than equal to mid and J less than equal to upper bound fine now next next condition is what suppose we have reached J is greater than upper bound now we have already put all the elements of this sub list into this one but still some elements of this this sub list is remaining then what you will do you simply put all these elements here only so you have to check that condition also fine you know how to check that thing if now I am going to take suppose one condition is I am going to take this I has been reached to its beyond to its limit so suppose I is greater then mid because I should be less than equal to mid now I has been breached to greater than mid means I has been reached here or it means all the elements of this sub list has been put here only now only some some elements of this are remaining may be some elements of this list are remain fine so if this condition is there then then what you will do you will put now all the remaining leftover elements of this sub list to Haran so now what right while J less than equal to upper bound while J less than equal to upper bound on fine because if J is also greater than upper bound then no need to then obviously there is no left or element so no need to put these elements here on you fine so you will write down that condition also while J less than equal to upper bound fine then only you will put what in B of K you will put a or J and then you load jo j + + + k + + I'm short of the space that is why I am writing multiple statements in one line fine and here you'll enclose this while loop okay now second case is there here I has been reached to greater than this mid else here if has been closed else if J has J has reached to its upper bound limit beyond - it upper bound limit that is J is suppose now greater than upper bound so now what do you what you will do else else you will check else may be some elements some left or elements are there in this sub list so you will check while I less than equal to mid in that case you will you'll do it in B of K you will put a of I you will copy all the values here on you now fine and you will do I plus plus and ka plus plus this is ending of this while loop and this is ending of this else loop fine now see we have taken another array that is B and the original array is a so now this B suppose this is B so now this is sorted array you simply copy all these values to this a simply round right down of for like this for K is equal to lower bound K less than equal to upper bound and k plus plus and simply copy in a of K you will copy would be of K all the values from B do and this is done now and after that you will close this merge function okay I know this is very congested because I have a shortage of the space but I I hope you got the concept of this merge function and the time complexity for the small sort is both in worst case and best case it is order of n log n so I'll make another video on this time complexity half this time complexity is order of n log and both in quicksort and mergesort so this is all about merge sort algorithm see if you know the logic of this merge function then simply you can easily write down the coding for this merge sort this is the main funder this is the main you can see the backbone of this merge sort algorithm fine so this is all about merge so in next video I am going to discuss with you heapsort so till then bye-bye

Channel: Jenny's lectures CS/IT NET&JRF

Views: 620,030

Keywords: merge sort, merge sort algorithm, quick sort, bubble sort, heap sort, sorting algorithms, insertion sort, merge sort time complexity, ugc net computer science, GATE computer science, jennys lectures, dijkstra algorithm, computer science youtube, engineering, c programming, merge sort in c, jayanti khatri lamba, data structure, algorithms, floyd warshall algorithm, ds notes, study material, data structure and algorithms, selection sort

Id: jlHkDBEumP0

Length: 35min 28sec (2128 seconds)

Published: Sat Jun 15 2019