hey everyone welcome back to the channel I hope you guys are doing extremely well so this is another lecture from the stripers A to Z course in case here for the first time here this is India's most in-depth DS algo course why do I say that because this course has over 56 modules and we will be solving more than 400 plus problems in this particular DS algo course you can buy any of the paid courses on the market you can check out all the free courses on YouTube you will not find such a comprehensive course on DS I'll go throughout the market so in case you haven't checked it out there's a link in the description you can check out the entire course so in the previous video we have covered the step 2.1 module in this video we will be covering the algorithm merge sort but there is a slight prerequisite to this algorithm you should have covered the step 1.5 module just in case you haven't please go and check it out and guys we are attaching the notes to all the problems and the video solution will be coming over here like if you see this one the video Solutions are attached and you'll soon be attaching all the notes so please make sure you follow this particular sheet the link will be in the description so without waiting let's get started with the problem merge shot so what is merge sort it is nothing but one of the other sorting algorithms I must be thinking about striver till now you have taught us bubble shot insertion sort selection sort so why this another algorithm if you remember all of these three algorithms were taking bigo of n Square in order to sort an array this is where mer short is better martial takes a much much better time complexity we will be discussing the time complexity at the end of this video but as of now you need to understand that my shot is a much more optimized sorting algorithm now you know sorting algorithm is nothing but it will sort a given data structure if it has numbers it will sorted according to Numbers if it has characters it will sorted according to characters if it has strings it will sort it according link to these strings so as of now we know that my shot is a sorting algorithm so what will be the flow of the lecture the flow of the lecture will be first I'll explain the algorithm completely then I'll go to the pseudo code and since this is a recursive algorithm I will go to dry run the recursion so that it gets into your head so after this three steps you will be able to code this particular algorithm in any of the languages because I will be writing the pseudo code post this I'll be taking one of the languages and I'll be writing the main code again this is something which is not that important I will be focusing more on the first three steps so without waiting let's get started with the first step that is the explanation of the algorithm so in order to explain the algorithm I will take this particular example of an array which has a size of nine you need to remember two words in more short please remember that the algorithm means divide and merge please remember this divide and merge so as as you can see that this array consists of nine elements if I have to ask you a question how do you divide nine elements into two parts you'll be like okay there are two ways in which I can do it one is I'll say four numbers and five numbers that's one of the ways the other way you can say is five numbers and four numbers that's two ways in which you can divide nine why because nine is a odd number so that cannot be splitted into two equal parts that's why either you have to go four by five or five by four now you can follow any of the path I'll follow the five by four path so if I follow the five by four path what happens is this algorithm divides the array hypothetically very important word this algorithm divides the array hypothetically into two parts and says three one two four one and five two six four what do you mean by hypothetically when I will write the pseudo code I'll explain you okay so as of now this algorithm has divided the array into two parts one which has five elements and the other which has four elements I can say left part and the right part now what I will do is I'll always take the left part and I'll try to divide it again so let's try to divide it again if I try to divide it again what happens is it has five numbers remember this it has five numbers so you can divide it like two by three or three by two now since since in the first step I divided nine into five and four bigger smaller I'll follow the same pattern I'll follow the same pattern so that I can easily write a repeated of code now what I'll do is I'll try to divide it something like three one two and four one remember one thing you can also divide it as smaller greater that is completely okay how you divide it doesn't matter as long as you divide it okay but make sure you follow the same pattern like over here it was like over here if you see it was five four there is greater or smaller so follow the same pattern of division in the future as well for odd numbers okay so next three one two go ahead and divide it I follow the same pattern and let's see three one and two so it's like two slash one again I'll try to divide it and this time it has two numbers it's even so it gets divided into two equal parts so I'll divide it something like three and one now tell me one thing can this be divided further the answer to that is no we cannot because it's a single number and you cannot divide a single number so this is why you stop you say the moment I get a single number I stop and you perform the second half of the algorithm that states please merge them so what do you mean by merge that is three so I'll write three it's one so they are basically two hypothetical array consisting of one numbers so if there are two hypothetical arrays of one numbers and I want to make it a single array what will I do I'll say okay let's merge it and you try to merge it into a single array consisting of these two numbers but in a sorted way so if I have to say okay I have three I have one and if I have to fill the first position I have to make it sorted whom will I take will I take one will I take three the answer to that is I will take one if I take one next two is remaining three the merged it I'll explain much in detail as the array gets bigger but as of now what you can say is okay we come back we come back whenever it's a single element in both sides we come back we take them and we merge and on merging this will become one three this will become one three perfect now this three one two was divided into this portion and was divided into this portion can I see the left portion got itself sorted and on the right portion has a single element can a single element be further divided the answer to that is no so your next step will be very simple you will take 1 comma 3 and 2. so can I say these are two hypothetical arrays one is one comma three on the left one is two on the right and you'll try to merge them into a single because there are two hypothetical arrays and if you carefully observe the left array in itself is sorted and the right array in itself is sorted so now I will go across and hypothetically try to merge them if I try to merge them they will give me three elements in the sorted order now tell me one thing do you take one or do you take two in order to fill this first position you'll be like hey stripper I will take one so you took one and you did not take two so the moment you've taken one the next you will say do I take three do I take two like I'll take two so you took two next year just left with one so you will take three again I'll explain this algorithm in depth do not worry so we basically merge them again merge them so we get one two three the merging has completed so can I see initially when I went to the left we had one two three and when we went to the right we had four one so the left portion has divided and merged itself into a single sorted array it has it's time to go to the right let's go to the right so the moment you look at the right it has poor one so we again try to uh divide it so if you try to divide it it'll be four and one can I see we can stop over here because they are single elements and they cannot be further divided yes we cannot further divide them so what we do is we stop now if it is 4 if it is 1 and if you have to merge them into a single sorted array first one will come then four will come so what will happen is they will try to merge them and you will get 1 comma four so can I say can I say that this one went got it sorted this one went and got it sorted so basically now they both will come back because the left half is sorted and the right half is sorted if both of them are completely sorted what will happen so can I say it went left and it got itself sorted it went right it got itself sorted it's time to come back so they will get merged very simple so let's write it again one two three and one four and they will try to merge themselves into how many elements definitely yes five elements so let's kind of now try to get into the algorithm now you know this is the smallest element on the left half if I say there are two hypothetical arrays can I say on the left the smallest element is definitely on the beginning because both the arrays are sorted so we will take one we will take one we have one over here we have one over here I have to ask you which one will occupy this it can be any of the ones if I take any of the ones and maybe I'll just move it now if I have to ask you out of two out of one which will occupy this you know the answer it's one so you now move the pointer next if I ask you out of two out of four which one will occupy this you will be saying two so I'll move the pointer next if I ask you out of three out of four which one does occupy this particular guy if you like three and this will move out next if I ask which one will occupy this you'll be like fold and this moves out so apparently you've got this entire thing sorted so can I say this will become one one two three four done so this half is sorted so we started with nine numbers we splitted them into five on this side four on this side five guys are have been sorted by the algorithm divide divide divide and merge much much they got themselves sorted now it's about these four elements can I perform the same algorithm of divide and merge on these four I can so what I'll do is I'll again start because now it's the right half's turn to get sorted so I'll not again divide the four elements and if there are even elements how do they get divided into equal number of elements so it will become five comma two and six comma four five comma two will become five two so again can I say they will be sorted back into two five and now this one will take place so it'll be like six four again it will come back I'll say four six perfect now can I see this portion is sorted this portion is sorted so now they will come back and how will they come back let's write it out two five four six so both of them will get merged into how many elements four elements two or four which one goes at the first two four or five four or five whole sorry uh now six or five yes five next six it's like two four five six very simple so this becomes two four five six we can go ahead and erase this as well got a bit clumsier but I'm I'm assuming you're getting the explanation now where are we can I see we went to the left we got everything sorted we went to the right we got everything sorted the left the left five elements are sorted the right four elements are sorted what is that we need to do we need to merge them we need to perform the last step that is merge so these one one two three four one one two three four and on the right we have two four five six we have two four five six they will get merged into nine elements and that will be my ultimate sorted array how do we emerge let's Now understand the algorithm in depth so what we do is we keep couple of pointers one here one here okay and then we create an array of size let's say 9. one two three four we created an array of size nine or you can create an MTR and keep on piling it up that's your choice we will take care of that during the implementation so we know this entire left array is sorted we know the entire right array is sorted so we have to combine them to get a sorted array so out of one and out of two because both of them are smallest I know I've taken the two smallest guys from left from right which one will take this place you say one so you take one and you place it and the moment you've taken someone you'll just move the pointer let's start start moving the pointer all right you take one or you take two again you take one and you move the pointer you take two or you take two you can take two and you can move the pointer you'll take three or you'll take two you'll take two and it'll move the pointer now will you take four will you take three you'll take three and you'll move the pointer now will you take four or will you take four you can take four and you can move the pointer so we can say the left array has been exhausted please hear me properly I can say the left array is completed it doesn't have any more elements that can go over here so what I will do is without doing any further comparisons I'll pick up everyone from the right and I'll just put it over here I'll pick up everyone from the right and I'll put it over here because there is no one left on the left got it if something similar happened that the right element got completed then you would have taken this and you'd have put it in doesn't matter so it's very simple if I have to define the merge algorithm it's very simple you take two pointers compare put put put one gets completed the other one gets put we will implement this do not worry so we have done the Sorting so the last step what will happen they come back they come back and this will be one one two two three four one one two two three four four five six four four five six so can I see after I have completed all the steps of divide and merge if you carefully notice the last step was merge in the entire algorithm so once I performed both of them completely on all the parts of the array the array that I get will always be sorted this was the algorithm I hope you have understood the explique okay so I hope you have understood the explanation it's time to understand the pseudocode first thing that we have to observe is what are we doing we are dividing we are dividing the array into two halves but logically speaking if you are going to break the break the array down into two new arrays and then again this array into two new arrays again this array into two new arrays well it makes sense no this is where in the pseudo code we will try to play around with index instead of breaking them down into two new arrays we will try to play around with indexes okay so in order to write the pseudocode what I've done is I've taken a very small array of size 5. I know the error indexing starts from 0 and it will go till 4 if the size is five so what I will say is C this index will be referred as Milo this index will be referred as high so what does low and high means is a starting point of an hypothetical array and high is the ending point of an hypothetical array so initially we have an entire array that has to be sorted so low is the starting point of that entire array and high is the ending point of that hypothetical array got it okay so let's try writing the pseudocode for this short algorithm so I'll go ahead and write the function name as merge sort and initially I'll pass the array and I will say in this array initially please consider the entire array that you have to sort so the hypothetical starting point of this array is low and this is high which means take the entire array so I'll pass him low and I'll pass him high and initially when this is called Low will be passed as 0 I will be passed as poor very simple let's go on and as of now I will not write any condition I'll keep conditions apart so how do I write this algorithm let's try to observe something what are we doing repeatedly are we doing something repeatedly yeah divide divide divide divide we're kind of doing divide divide divide divide another last step we're trying to come back come back does it give you an idea that you have to apply something like a recursion like you have to go divide divide divide and then you have to come back that's kind of like recursion backtracking if you have seen the lectures you can try to relate it with recursion and backtracking that's what we will be using so what I will say is okay now what is the thing that I'll do I'll try to take this array and try to break it down into two parts that is what I'm doing I'll try to take this array and I'll try to break it down into two parts where I will take the first one to be three to four that's how I was doing the greater like three numbers at the first and then the two numbers at the back so I'll say I'll divide it into two parts the left and the right that's what I'm doing and then I'll ask can you please sort this can you please sort this once both of them are sorted I can actually again merge them that's what the algorithm was so I'll be like okay do I need to make a new array no this is where low and high comes in I say Hey listen this is array indexing so can I say this array is nothing but an array where the low is at zero an array where the high is at two can I see this I can so if I have to look properly the low is at zero the high is at two that's what I'm doing so I'll go and say that here listen maybe find a middle index so middle is going to be low plus High by 2. very simple so if you see over here what will be this 0 plus 4 by 2 will give you 2. so where is the first half of the array it's from 0 till 2. and where's the second half it's from three to four so can I say hey please go ahead and try to sort this array sort this array which starts from 0 which is apparently low and this goes on till 2 which is apparently middle because in the first time the middle is two and can I see okay this means I'm I'm asking him to do for this one right but I have to also ask him to do for this one because if he sorts this if he doesn't Swatch this how will I merge that because both of them have to be sorted in order to be merged so what I will do is I'll again say merge shot I'll say Ari can I get the right half of the array software okay in this array which portion are you telling me to sort I'm saying from three to four what is three that's nothing but mid plus one because mid was two until high so what I've done is instead of making two new arrays I told the indexes I told in this array take from low to mid which is take from 0 to 2 which is this in this array take from three to four which is this instead of dividing them into two arrays I passed on the indexes and set them to one set them to sort themselves now assuming that these functions are getting sorted by themselves once the portion from low to mid once the portion from low to mid is sorted once the portion from mid one to high is sorted what is the next step if you remember the next step is merge so probably I can say that hey please go ahead and merge the array the first half of the array is very simple it goes from low to mid and the second half will be from mid plus 1 to high so take these things and can you please merge this particular array that's what I'm saying that's what I'm saying very simple now when do we stop when do we stop is my question we have to write that over here because if you know if this is nothing but a recursion my shot calling itself my short calling itself it's a recursion in order to stop recursion you write something as base case I hope you know that in order to stop recursion you write something as base case so you have to write that base case let's analyze what is the base case let's go back to this example what is the Beast case can I see when your array has one element when the array has one element so if I have to index it can I say this is index 0 this is index 1 this is index three two three four five six seven eight can I say these are the last indexes and if I have to ask what array is this you'll be like this array is something like from index 1 to index 1 where index 1 is the low index one is the high can I say this is the array that represents this yes because we are not creating a new array I am saying this array is from index 1 to index 1 which is this so can I say the moment we have the low the left point we have the high the right point to be same that's when we do not go and divide we do not divide we just go back so that's what the base case will be we write a if at any moment the low tends to be equal to equal to high or exceeds high for that reason or maybe it's some how like it will never but still there's no safety reasons if it exceeds High please do not because there's no need to do any of the further algorithms it's a single element array and it will always be sorted please go back please go back so this is how the pseudo code will look like might seem a bit confusing but now when I'll Rewind by taking an example straight away I get to your head okay so we can see that the pseudo code has been completed but in order to understand this algorithm with Clarity we have to do a dragon of this recursive algorithm then only it will get clarified so let's try to do a dry run by taking this particular example so remember one thing whenever this algorithm is called it is called with the complete array so the entire array has always been passed with this algorithm and the initial low and high will be 0 and 4 because that's what for this particular example it will be because in initially I will pass on this entire array and ask Mass shot to sort it so what will happen will this first base case operate because no low is still smaller than high so it doesn't mid comes out what will be the value of mid can I say the value of mid will be 2. so what happens is it goes ahead and calls the merge shot it goes ahead and calls the merge shot so let's copy paste the same algorithm let's do it so I've copy pasted so what we can say is this particular recursion call will call this particular function again but this time it will pass the low as 0 and pass the highest 2. so apparently what happens is it calls for this guy remember our recursion works is first this will get operated comes back then this line gets operated that's how recursion works so that's why first the left portion will get operated so the recursion call for 0 to goes now what happens does this line operate no this line doesn't operates what happens tries to find the mid and this time the mid comes out to be 1 because 0 plus 2 is 2 and 2 by 2 as 1 so 1 comes up so this time again the small shot gets called but if if the merge shot gets called what will happen it gets called for what from zero to one so it's like three to two is what it is getting called and then it will be called for the only number four which is just two so we will go ahead and maybe again call this recursion let's go ahead and call the recursion again so the recursion is again called what happens this time the motion is called with 0 1 which means this particular example right so this time the low is 0 the highest one so what happens the mid is 0 plus 1 by 2 which is nothing but 0. so again the motion is called so let's again copy paste this same algorithm the more short this time is called for 0 0. if I go into the diagram it's something like for three and something like for just one so this time it's called for three so what happens is it's called for 0 and 0. so apparently this particular base case gets executed and it returns so I can say the it's done it's done if I have to go back into the chart this goes back similarly another more shot will be called let's try to write this as well and this time it will be called for from mid plus 1 to high submit was 0 it'll be like 1 comma 1 because high was one mid was 0 so bit plus one is one high is one so high is one it's called for one comma one again the low the base case operates and it calls back apparently both of these recursive functions are completed once both of these recursion functions are completed can I say this that I am going back from here and now we have this as sorted we have this assorted two sorted arrays it's two sorted arrays what will happen let's go back here this merge happens so it takes a three it takes a two and it tries to merge it now we will write the merge algorithm afterwards but let's understand just imagine mergers merging two Aries that's it that's a very simple algorithm just understand this so 2 comma 3 happens so what would have happened two comma three right so this would have become 2 comma 3 perfect let's go back to the recursion so can I see now we can go back from here to here and we can say the 0 1 is sorted so this time this recursion will again be called let's try to write it so what will be this precaution if 0 1 is done sorry my bad if 0 1 is done what's the next mid plus 1 that's 2 is 2 so I'll call it for 2 comma 2 and if we call it for 2 comma 2 what will happen yes they are the same numbers so it will return and if it returns this time what will happen it called for two comma two this guy has done the recursion and this guy has done the recursion so apparently again the merge happens this time the merge happens from zero to one till the two the March this time happens for two comma three and maybe four or whatever it is yes and this will become 2 comma 3 comma four I hope you are getting the gist so can I say after this I'll again go back and when I go back I'll try to just come back kiss when I go back can I see this that zero comma two would have been sorted and if 0 comma 2 is sorted I'm done with this and I'll go to the right part which is having this and similarly this is done so this will call it right and how will it call it let's copy paste and show it if 0 comma 2 has been done so can I say next is mid plus one so this is nothing but three highest four this time it goes and calls for three comma four again the same thing will happen the mid will be like three plus four seven by two three so it'll be called for three comma 3 and then it'll come back this will be called for four comma four it'll be come back and then this will merge both of these two elements it's like it will be called for one it'll be called for three then they will be merged as one three and once this is done what do we have we have 0 comma 2 sorted we have three comma 4 sorted so the last merge takes place between this 0 comma 2 that is 2 comma 3 comma four and one comma three so apparently they are merged together when merged you will get one two three three four the that is what happens at the last step I hope that does make sense so so I hope that Ryan is clear in terms of the pseudocode it was very simple first the entire array goes to the left goes to the left goes to the left goes to the left and then merges it always performs this recursion first this precaution first this recursion first once this is completed then this once both are completed then the merge happens you need to understand so this is how the flow Works in order to understand this in much more depth what I'll recommend you is take a pen and paper write this code try doing it all over again got it so what have we completed we have completed the dry run the pseudo code as well but before going into the code we still are left with the merge sudo code if we are able to write the merge pseudocode I think we will be done so let's take a bigger example in order to understand the merge sudo code can I say the indexing is like 0 1 2 3 4 5 6 7 8 and this is like zero one two three four and this is like five six seven and eight and if the merge will happen I will call it like merge these two areas because if you know this array when goes into depth goes into depth it will be sorted it'll be sorted like one one two three four and this also will go into the depths and it will be sorted like two four five six this is something which all of us know for sure that both of them will be sorted and both of the array will be something like one 11234 and this will be like two four five six this is something we know and this will be index from 0 to 4 this will be from five to eight that's something we know we just have to write an algorithm to do it so we're writing the algorithm okay so we're saying merge I'll give you the array and I'm stating you that the first half is from low to mid and then you can go from mid plus one to high so I'm giving you all the three parameters required what I'll do is maybe I'll just keep in empty data structure it can be a vector it can be a list as of now just imagine this is an empty data structure where we can add elements okay now can I see that the left array will be from low to mid and can I say the right array will be from mid plus 1 to high I can so I will keep couple of pointers so I'll say okay left pointer is at the low so that means left comes over here and I'll say right pointer is nothing but at Mid plus one so what happened I'll say right is here now what will I do I will try to compare these two and try to fill in this bigger array the bigger array I'll try to do compare these two and try to fill in the bigger array so what I will do is I will now try to I treat till what till we have elements on the left or till we have elements on the right can I say that means I will say while left is smaller than equal to Mid which means I still have element LC and and right is lesser than equal to high which means I still have elements on the right very simple now what I'll do is okay this is what I'll do till I have elements on the left till I have elements on the left on the right so I'll now try to compare I will say Hey listen if array of left is smaller than equal to array of right so what happens this and this gets compared and if one is smaller than 2 I'll take one and I'll add it to our resultant guy I'll add it to our resulting guy so I'll say okay maybe uh we can name this as something else let's go and name this as maybe let's say temporary that's a better name I'll say temporary can you please add yourself the smaller guy array of left and once you have done this can you move ahead the pointer which means the left pointer goes to the next again so basically what will happen is now temporary will have one with itself again the comparison between one and two will happen and this one will come here the temporary again takes it and now the left moves here again the comparison between 2 and 2 will happen and it comes here and the left moves here this time when you compare 3 and 2 when you compare 3 and 2 the 2 will come but the if only Compares for lesser so there will be else so else will state can you please add the right guy can you please add the right guy that is take from the array and add the right guy and once you have added can you move the right plus plus so what I'll do is I'll move the right to a head now that's how this will work and it'll keep on comparing and he'll keep on adding till this is not completed so what will happen this two will come and the right will move here now the comparison between 4 and 3 happens so three comes and the left moves here now four comes and the left is exhausted left exceeds mid left exceeds mid so we see that left has exceeded mid there is no one on the left so what I will say is after the end if there is anyone on the left which means if there is anyone on the left because if this while if this while loop is false either it will be false because this is true or this is true so if there are on the left if there are on the left I will still add it I'll just take every one from the left and add it to my stuff and if there are people on the right because any one will be true either there will be on the left either there will be on the right if there are people on the right which will be right high and then I'll say temporary dot add array of right and I'll do right plus plus quite simple if that means if on left copy them if on right copy them as simple as that so can I say at the end of the day I would have four four five six all of them in the temporary array now we need to place them into the original array so what have we completed till this step we can say the left sorted array and the right sorted array have been put into a third array temporary but we actually need to put it from low to high because that's the original array because the original array is from 0 to 8 and if you take these elements and put it there because it is in temporary so what I'll do is I will probably Loop yes let's Loop I'll say for I from low to high is where I Loop please loop from there and I'll say array of I that means who is the first element temporary temporary must be keeping because it's a temporary array it will always keep in the zeroth index so I'll always say temporary I minus low that's it first time I will be low so what will this happen low minus low that will be zero next time I will be low plus 1 so low plus 1 minus low that'd be one next time I will be low plus 2 low plus 2 minus low I'll be two so it will get all these indexes because it will be stored in a temporary array it will pick up all these indexes and store in the correct order so I will pick up all these indexes at 0 1 2 and store it in the correct order from low to high because because this was glutamate this was mid plus 1 to I and they got together from low to high that was the original array got it this is how the merge will look like I hope that does make sense so now I can confidently say that you've understood the explanation the pseudo code and the dry run so you can code it in C plus plus Java and python so I'll just go across and code it in C plus plus or the Java and python codes you can find them in the links in the description it will be updated very very soon just in case it is not there as of now let's come to the compiler and try to code it so we have given a function we're given the array and we're given this so assume we are going to write this function and we say void uh more short and I'll say let's take the array which is this please make sure you pass it by reference slow and high that's what we require and we know one thing if low is equal to high we're going to return that's it otherwise we're gonna find a middle which is low plus High by two and then we will be calling the MS with array comma Loop comma mid and Ms array comma mid plus 1 comma high and then we will be calling something like merge where it will be passing array low mid and high that's what the algorithm will be and we can call Ms where the array and zero command minus 1 because that's the initial starting and the end position of the entire array just have to write the merge function and I think we will be done so let's write the void merge and again make sure you take everything by reference array and then low and then you can say commit and then you can take High so can I just take a temporary array we can we can take the left pointer to be low plus 1 uh sorry low rather and you can take the right pointer to be mid plus one because we know the first array will be like if I have to comment it it will be from low to mid and the second array if you remember it will be mid plus 1 till High so let's see uh let's write this so we say left is less than equal to Mid and and made and and right is less than equal to high very simple but we need a temporary array that is defined over here we say hey array of left are you smaller than array of right if you are can you please go ahead and get attached push back to array of left very simple at the same time you can do a left plus plus and you can write an else and you can temporary dot push back array of right and you can say right plus plus this is what you will do for comparing and putting it after that if there are still elements left on the left please take it because if this is false then this must be having some elements on the left so go ahead and just copy paste this perfect and if there are still elements on the right then go ahead and copy paste everything from the right quite simply once you have done this make sure you put them into the array which is for Indi equal to low I less than equal to high and I plus plus and you can say array of I will be temporary of I minus low so once you've done this since everything is by reference the at the numbers will rearrange themselves in the array itself now I can go ahead and go ahead and run this and see if it is running fine I hope it does it does and now I'll quickly submit this I write quotes in one Goa no syntax errors so we have understood everything but there's only one thing that is left which is the time complexity of this merge short algorithm remember one thing what's happening there's an end size array which is getting divided to n by 2 N by 2 then this n by 2 is getting divided to n by 4 n by 4 n by 4 and N by 4. so at every step the getting divided by two by two by two by two and if you remember the time complexity lecture I have already told whenever it gets divided by by 2. the time complexity is log base to n remember this now you might ask me but Trevor why you're dividing it by by two by two but why it is log base 2 N it's very simple if I have to write 16 and I have to divide it by 2 it'll be like 8 and 8. it'll be like four and four right like if there are four like if there are 16 array elements gets divided into eight and eight it gets divided into four and four four gets into two and two and then 2 gets into one and one so apparently this is nothing but one step two step three step four step and 16 is nothing but 2 to the power 4 and that's nothing but four steps right four steps log base 216 is nothing but four steps so it's approximately logarithmic number of times the division happens it's approximately logarithmic number of times that the division happens that means it gets broken down into logarithmic of n type and you're also performing something like a merge every time so every time division by like this is div this is half and this is half this half Will Go On Till log base to n near about again everything is in terms of near about okay time complexities goes till near about log base 2. and then there is a merge happening how much is merge taking if I have to think of the extremist keys if I have to think of the extremist case can I say this is of size three this is of size 2. so in order to merge three and two elements I'm gonna require five steps at minimum one comparison that's like everyone is comparing in itself it's like a near about big go of n that's a worst case because for this I'll end up taking at minimum of five steps because every element is compared one by one and then it is put over here so it takes minimum of five steps which is nothing but the length of the array at the worst case so can I say the merge I have to go back to this uh there's so many things written man I have to go back this can I say this at the worst case takes big offend this time over here it might take big of n by two over here it might take n by 4 something like this but the worst case it is taking n so thereby I can actually say that the time complexity is nothing but n into log base 2 N now you might ask me question a question but straight away one step two step three step four step two will be counting these steps wait that is actually compensated how because the merge over here takes big oven the merge over here takes n by 2. the merge over here will take n by four the merge is taking lesser so in overall if you try to add it up in mathematical you will actually get somewhere near about n into log base 2 and as the merge shots time complex so n log n is the best average and the worst case but if I have to ask okay what is the space complexity of the algorithm how much extra space are we using so if you remember the algorithm the algorithm is actually using indexes no separate Aries is this the given area that they are using are they using any extra additional space they are during merge in every merge step they're creating a temporary array which are the worst case might take big of n so the space complexity at the worst case is bigo of n near about B go of n for this particular algorithm so with this I will be completing merge shot and the time is 3 28 am in the morning as you can see I cannot record in the day because there's a lot of background noise so just in case you understood everything please please consider hitting that like button and if you haven't checked out stravacito's at DSA course the link will be in the description please make sure you check it out because we have notes for everything we will be attaching video solutions to everything yes most of the advanced topics have been covered previously I am starting to cover the basic topics now so you can definitely proceed ahead with the advanced Topics in case you need for Advance as well so guys if you're new to our Channel please do consider hitting that subscribe button because that is the only thing that keeps you motivated to make these kind of videos and you have to follow our tradition please make sure you comment understood in the comments so that I get a vibe that you guys are understanding everything so with this I'll be wrapping up this video If you haven't followed me on Instagram Twitter LinkedIn the links will be in the description with this let's wrap up this video and made out some other videos [Music]