YT YouTube2Text

YouTube2Text → Transcripts → Merge Sort | Algorithm | Pseudocode | Dry Run | Code | Strivers A2Z DSA Course

Merge Sort | Algorithm | Pseudocode | Dry Run | Code | Strivers A2Z DSA Course — Transcript

by take U forward · 8,560 words · 1,087 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:03hey everyone welcome back to the channel
0:04I hope you guys are doing extremely well
0:06so this is another lecture from the
0:07Strivers a toz course in case you're for
0:10the first time here this is India's most
0:12in-depth DS algo course why do I say
0:14that because this course has 456 modules
0:17and we will be solving more than 400
0:19plus problems in this particular DS algo
0:22course you can buy any of the paid
0:23courses on the market you can check out
0:26all the free courses on YouTube you will
0:28not find such a comprehensive course on
0:30DS algo throughout the market so in case
0:34you haven't checked it out there's a
0:35link in the description you can check
0:36out the entire course so in the previous
0:39video we have covered uh the step 2.1
0:41module in this uh video we will be
0:43covering the algorithm merge sort but
0:46there is a slight prerequisite to this
0:48algorithm you should have covered the
0:50step 1.5 module just in case you haven't
0:53please go and check it out and guys we
0:56are attaching the notes to all the
0:59problems and the video solution will be
1:01coming over here like if you see this
1:02one the video Solutions are attached and
1:04we'll soon be attaching all the notes so
1:07please make sure you follow this
1:08particular sheet the link will be in the
1:11description so without waiting let's get
1:12started with the problem merge short so
1:15what is merge sort it is nothing but one
1:18of the other sorting algorithms you must
1:21be thinking but striver till now you
1:23have taught us bubble short insertion
1:26sort selection sort so why this another
1:29algor Alm if you remember all of these
1:31three algorithms we're taking B go of n
1:33squ in order to sort an array this is
1:37where M short is better mot takes a much
1:40much better time complexity we will be
1:42discussing the time complexity at the
1:44end of this video but as of now you need
1:46to understand that mot is a much more
1:49optimized sorting algorithm now you know
1:52sorting algorithm is nothing but it will
1:54sort a given data structure if it has
1:56numbers it will sort it according to
1:57Numbers if it has characters it will
1:59sort it according to characters if it
2:01has strings it will sort it according to
2:03the strings so as of now we know that
2:05mot is a sorting algorithm so what will
2:08be the flow of the lecture the flow of
2:09the lecture will be first I'll explain
2:12the algorithm completely then I'll go to
2:15the pseudo code and since this is a
2:19recursive algorithm I will go to dry run
2:22the recursion so that it gets into your
2:24head so after this three steps you will
2:27be able to code this particular
2:29algorithm in any of the languages
2:31because I will be writing the pseudo
2:32code post this I'll be taking one of the
2:35languages and I'll be writing the main
2:37code again this is something which is
2:39not that important I will be focusing
2:42more on the first three steps so without
2:44waiting let's get started with the first
2:46step that is the explanation of the
2:47algorithm so in order to explain the
2:49algorithm I will take this particular
2:50example of an array which has a size of
2:54nine I need to remember two words in M
2:57short please remember that the algorithm
2:59means means divide and merge please
3:04remember this divide and merge so as as
3:09you can see that this array consists of
3:11nine elements if I have to ask you a
3:14question how do you divide nine elements
3:16into two parts you'll be like okay there
3:19are two ways in which I can do it one is
3:21I'll say four numbers and five numbers
3:25that's one of the ways the other way you
3:28can say is five numbers numers and four
3:31numbers that's two ways in which you can
3:34divide nine why because nine is a odd
3:38number so that cannot be splitted into
3:41two equal parts that's why either you
3:43have to go 4X 5 or 5 by4 now you can
3:47follow any of the path I'll follow the
3:495x4 path so if I follow the 5x4 path
3:52what happens is this algorithm divides
3:54the array hypothetically very important
3:57word this algorithm divides the array
3:59hypothetically into two parts and says 3
4:021 2 4
4:041 and 5 2 6 4 what do you mean by
4:08hypothetically when I will write the
4:10pseudo code I'll explain you okay so as
4:12of now this algorithm has divided the
4:14array into two parts one which has five
4:17elements and the other which has four
4:19elements I can say left part and the
4:21right part now what I will do is I'll
4:23always take the left part and I'll try
4:25to divide it again so let's try to
4:27divide it again if I try to divide div
4:29it again what happens is it has five
4:32numbers remember this it has five
4:34numbers so you can divide it like 2x 3
4:37or 3x2 now since since in the first step
4:41I divided N9 into five and four bigger
4:45smaller I'll follow the same pattern
4:47I'll follow the same pattern so that I
4:49can easily write a repetitive code now
4:52what I'll do is I'll try to divide it
4:53something like 312 and
4:5641 remember one thing you can also div
4:59divide it as smaller greater that is
5:02completely okay how you divide it
5:04doesn't matter as long as you divide it
5:06okay but make sure you follow the same
5:09pattern like over here it was like over
5:12here if you see it was 54 it is greater
5:14smaller so follow the same pattern of
5:16division in the future as well for odd
5:19numbers okay so next 312 go ahead and
5:22divide it I follow the same pattern and
5:24let's say 31 and two so it's like 2/ one
5:29again I'll try to divide it and this
5:32time it has two numbers it's even so it
5:36gets divided into two equal parts so
5:39I'll divide it something like three and
5:42one now tell me one thing can this be
5:45divide it further the answer to that is
5:48no we cannot because it's a single
5:49number and you cannot divide a single
5:52number so this is where you stop you say
5:55the moment I get a single number I stop
5:59and you perform the second half of the
6:01algorithm that states please merge them
6:04so what do you mean by merge it is three
6:07I'll write
6:08three it's one so they are basically two
6:11hypothetical array consisting of one
6:14numbers so if there are two hypothetical
6:17arrays of one numbers and I want to make
6:19it a single array what will I do I'll
6:22say okay let's merge it and you try to
6:25merge it into a single array consisting
6:28of the two numbers but in a sorted way
6:32so if I have to say okay I have three I
6:34have one and if I have to fill the first
6:36position I have to make it sorted whom
6:39will I take will I take one will I take
6:41three the answer to that is I will take
6:44one so I take one next who is remaining
6:47three I've merged it I'll explain merge
6:50in detail as the array gets bigger but
6:52as of now what you can say is okay we
6:55come back we come back whenever it's a
6:57single element in both sides we come
6:59back we take them and we merge and on
7:02merging this will become 1 three this
7:05will become 1 three perfect now this 312
7:09was divided into this portion and was
7:12divided into this portion can I say the
7:16left portion got itself sorted and now
7:19the right portion has a single element
7:22can a single element be further divided
7:25the answer to that is no so your next
7:27step will be very simple you will take
7:301A 3 and two so can I say these are two
7:34hypothetical arrays one is 1A 3 on the
7:37left one is two on the right and you'll
7:39try to merge them into a single because
7:42there are two hypothetical arrays and if
7:44you carefully observe the left array in
7:47itself is sorted and the right array in
7:51itself is sorted so now I will go across
7:54and hypothetically try to merge them if
7:56I try to merge them they will give me
7:59three elements in the sorted order now
8:01tell me one thing do you take one or do
8:04you take two in order to fill this first
8:07position you'll be like hey dri I will
8:09take one so you took one and you did not
8:13take two so the moment you've taken one
8:16the next you will say do I take three do
8:18I take two like I'll take two so you
8:21took two next you just left with one so
8:24you will take three again I'll explain
8:26this algorithm in depth do not worry so
8:29we
8:30basically merge them again merge them so
8:33we get 1 2 3 the merging has
8:38completed so can I say initially when I
8:41went to the left we had 1 2 3 and when
8:44we went to the right we had 41 so the
8:47left portion has divided and merged
8:51itself into a single sorted array it has
8:55it's time to go to the right let's go to
8:57the right so the moment you look at the
8:59right it has 41 so we again try to uh
9:04divide it so if you try to divide it it
9:06will be four and one can I say we can
9:10stop over here because they are single
9:12elements and they cannot be further
9:14divided yes we cannot further divide
9:17them so what we do is we
9:19stop now if it is four if it is one and
9:23if you have to merge them into a single
9:27sorted array first one will come then
9:29four will come so what will happen is
9:31they will try to merge them and you will
9:33get one comma four so can I say can I
9:37say that this one went got it sorted
9:41this one went and got it sorted so
9:43basically now they both will come back
9:46because the left half is sorted and the
9:48right half is sorted if both of them are
9:51completely sorted what will happen so
9:54can I say it went left and it got itself
9:57sorted it went right it got itself
10:00sorted it's time to come back so they
10:04will get merged very simple let's write
10:07it again 1 2 3 and 1 4 and they will try
10:12to merge themsel into how many elements
10:15definitely yes five elements so let's
10:19kind of now try to get into the
10:21algorithm now you know this is the
10:22smallest element on the left half if I
10:25say there are two hypothetical arrays
10:27can I say on the left the small smallest
10:29element is definitely on the beginning
10:31because both the arrays are sorted so we
10:34will take one we will take one we have
10:37one over here we have one over here but
10:40I have to ask you which one will occupy
10:43this it can be any of the ones I take
10:45any of the ones and maybe I'll just move
10:48it now if I have to ask you out of two
10:51out of one which will occupy this you
10:55know the answer it's one so you now move
10:57the pointer next next if I ask you out
11:00of two out of four which one will occupy
11:03this you will be saying two so I'll move
11:06the pointer next if I ask you out of
11:08three out of four which one does occupy
11:12this particular guy it like three and
11:14this will move out next if I ask which
11:16one will occupy this you'll be like four
11:18and this moves out so apparently you got
11:21this entire thing sorted so can I say
11:24this will become 1 1 2 3 4 done
11:31so this half is sorted so we started
11:35with nine numbers we splitted them into
11:39five on this side four on this side five
11:43guys are have been sorted by the
11:45algorithm divide divide divide and merge
11:48merge merge they got themselves sorted
11:50now it's about these four elements can I
11:53perform the same algorithm of divide and
11:55merge on these four I can so what I'll
11:59do is I'll again start because now it's
12:01the right half turn to get sorted so
12:04I'll not again divide the four elements
12:06and if there are even elements how do
12:09they get divided into equal number of
12:10elements so it will become 5 comma 2 and
12:146 comma 4 5 comma 2 will become 5 2 so
12:20again can I say they will be sorted back
12:23into
12:2525 and now this one will take place so
12:29be like 6 4 again it will come back I'll
12:34say 4 6 perfect now can I say this
12:37portion is sorted this portion is sorted
12:40so now they will come back and how will
12:42they come back let's write it out 25 4 6
12:46so both of them will get merged into how
12:49many elements four elements two or four
12:52which one goes at the first two four or
12:56five four or five four
13:01sorry uh now six or five yes 5 next six
13:09it's like 2 456 very simple so this
13:12becomes 2 456 we can go ahead and erase
13:15this as well got a bit clumsier but I'm
13:18I'm assuming you're getting the
13:19explanation now where are we can I say
13:23we went to the left we got everything
13:25sorted we went to the right we got
13:27everything sorted the left left the left
13:30five elements are sorted the right four
13:32elements are sorted what is that we need
13:35to do need to merge them you need to
13:37perform the last step that is merge so
13:39these 1 1 2 3 4 1 1 2 3 4 and on the
13:45right we have 2 4 5 6 we have 2 4 5 six
13:49they will get merged into nine elements
13:52and that will be my ultimate sorted
13:55array how do we merge let's Now
13:58understand the algorithm in depth so
14:00what we do is we keep couple of pointers
14:03one here one here okay and then we
14:06create an array of size let's say nine 1
14:102 3 4 5 6 we created an array of size 9
14:15or you can create an Mt and keep on
14:17piling it up that's your choice we will
14:20take care of that during the
14:21implementation so we know this entire
14:25left array is sorted we know the entire
14:27right array is sorted so so we have to
14:30combine them to get a sorted array so
14:33out of one and out of two because both
14:35of them are smallest I know I've taken
14:38the two smallest guys from left from
14:40right which one will take this place you
14:43say one so you take one and you place it
14:46and the moment you've taken someone
14:48you'll just move the pointer let's start
14:50start moving the pointer got it and you
14:52take one or you take two again you take
14:54one and you move the pointer you take
14:56two or you take two you can take two and
14:58you you can move the pointer you'll take
15:00three or you'll take two you'll take two
15:02and you'll move the pointer now will you
15:04take four will you take three you'll
15:06take three and you'll move the pointer
15:07now will you take four or will you take
15:09four you can take four and you can move
15:11the pointer so we can say the left array
15:15has been exhausted please hear me
15:18properly I can say that the left array
15:21is completed it doesn't have any more
15:24elements that can go over here so what I
15:26will do is without doing any further
15:29comparisons I'll pick up everyone from
15:31the right and I'll just put it over here
15:34I'll pick up everyone from the right and
15:37I'll put it over here cuz there is no
15:39one left on the left got it if something
15:43similar happened that the right element
15:45got completed then you would have taken
15:47this and you have put it it doesn't
15:49matter so it's very simple if I have to
15:53define the merge algorithm it's very
15:54simple you take two pointers compare put
15:57put put one gets comp completed the
15:59other one gets put we will implement
16:02this do not worry
16:04so we have done the Sorting so the last
16:07step what will happen they come back
16:09they come back and this will be 1 1 2 2
16:133 4 1 1 2 2
16:173 4 4 5 6 4 4 5 6 so can I see after I
16:24have completed all the steps of divide
16:27and merge if you carefully notice the
16:29last step was merge in the entire
16:32algorithm so once I performed both of
16:34them completely on all the parts of the
16:37array the array that I get will always
16:41be sorted this was the algorithm I hope
16:44you have understood the expl okay so I
16:45hope you have understood the explanation
16:48it's time to understand the pseudo code
16:50first thing that we have to observe is
16:53what are we doing we are dividing we
16:56dividing the array into two halves but
16:59logically speaking if you're going to
17:01break the uh break the array down into
17:03two new arrays and then again this array
17:06into two new arrays again this array
17:08into two new arrays will it makes sense
17:11no this is where in the pseudo code we
17:15will try to play around with index
17:19instead of breaking them down into two
17:22new arrays we will try to play around
17:24with indexes okay so in order to write
17:27the pseudo code what I've done is is
17:29I've taken a very small array of size
17:31five now you know the array indexing
17:33starts from zero and it will go till
17:35four if the size is five so what I will
17:39say is see this index will be referred
17:43as my low this index will be referred as
17:48high so what does low and high means is
17:50a starting point of an hypothetical
17:52array and high is the ending point of an
17:55hypothetical AR so initially we have an
17:58entire aray that has to be sorted so low
18:01is the starting point of that entire
18:03array and high is the ending point of
18:06that hypothetical array got it okay so
18:08let's try writing the pseudo code for
18:09this merge short algorithm so I'll go
18:12ahead and write the function name as
18:14merge sort and
18:17initially I'll pass the array and I will
18:20say in this array initially please
18:24consider the entire array that you have
18:26to sort so the hypothetical starting
18:29point of this array is low and this is
18:31high which means take the entire array
18:34so I'll pass him low and I'll pass him
18:37high and initially when this is called
18:40Low will be passed as zero high will be
18:43passed as four very simple let's go on
18:47and as of now I'll not write any
18:49condition I'll keep conditions apart so
18:53how do I write this algorithm let's try
18:56to observe something what are we doing
18:59repeatedly are we doing something
19:00repeatedly yeah divide divide divide
19:04divide kind of doing divide divide
19:06divide divide and at the last step we're
19:09trying to come back come back does it
19:11give you an idea that you have to apply
19:13something like a recursion like you have
19:15to go divide divide divide and then you
19:18have to come back that's kind of like
19:19recursion backtracking if you have seen
19:21the lectures you can try to relate it
19:23with recursion and backtracking that's
19:25what we will be using so what I will say
19:27is okay now now what is the thing that
19:29I'll do I'll try to take this array and
19:32try to break it down into two parts that
19:34is what I'm doing I'll try to take this
19:36aray and I'll try to break it down into
19:38two parts where I will take the first
19:42one to be 3 to 4 that's how I was doing
19:45the greater like the three numbers at
19:47the first and then the two numbers at
19:48the back so I'll say I'll divide it into
19:50two parts the left and the right that's
19:52what I'm doing and then I'll ask can you
19:55please sort this can you please sort
19:57this once both of them are sorted I can
20:00actually again merge them that's what
20:03the algorithm was so I'll be like okay
20:06do I need to make a new array no this is
20:09where low and high comes in I say Hey
20:12listen this is array
20:14indexing so can I say this array is
20:17nothing but an array where the low is at
20:20zero an array where the high is at two
20:22can I see this I can so if I have to
20:26look properly the low is at zero
20:29the high is at two that's what I'm doing
20:31so I'll go and say that Hey listen maybe
20:34find a middle index so middle is going
20:37to be low plus High by two very
20:40simple so if you see over here what will
20:43be this 0 + 4 by 2 will give you 2 so
20:48where is the first half of the array
20:51it's from 0 till 2 and where is the
20:54second half it's from 3 to 4 so can I
20:57say hey please go ahead
21:01and try to sort this array sort this
21:06array which starts from zero which is
21:09apparently low and which goes on till
21:11two which is apparently middle because
21:14in the first time the middle is two and
21:16can I say okay this means I'm I'm asking
21:20him to do for this one right but I have
21:24to also ask him to do for this one
21:25because if he sorts this
21:28if it doesn't sorts this how will I
21:30merge them because both of them have to
21:32be sorted in order to be merged so what
21:34I will do is I will again say mer
21:38short I'll say array can I get the right
21:42half of the array sof I'll be like okay
21:44in this array which portion are you
21:47telling me to sort I'm saying from 3 to
21:494 what is three that's nothing but mid +
21:521 because mid was two till high so what
21:55I've done is instead of making two new
22:00arrays I told the indexes I told in this
22:05array take from low to mid which is take
22:07from 0 to two which is this in this
22:09array take from 3 to four which is this
22:12instead of dividing them into two arrays
22:15I passed on the indexes and set them to
22:17set them to sort themselves now assuming
22:20that these functions are getting sorted
22:23by themselves once the portion from low
22:27to mid once once the portion from low to
22:30mid is sorted once the portion from mid
22:32one to high is sorted what is the next
22:35step if you remember the next step is
22:37merge so probably I can say that hey
22:41please go ahead and merge the array the
22:46first half of the array is very simple
22:48it goes from low to mid and the second
22:51half will be from mid plus one to high
22:53so take these things and can you please
22:56merge this particular array that's what
22:59I'm saying that's what I'm saying very
23:00simple now when do we stop when do we
23:03stop is my question we have to write
23:05that over here because if you know if
23:08this is nothing but a recursion mot
23:11calling itself mot calling itself it's a
23:13recursion in order to stop recursion you
23:17write something as base case I hope you
23:20know that in order to stop recursion you
23:22write something as base case so you have
23:24to write that base case let's analyze
23:26what is the base case let's go back to
23:28this example what is the Beast case can
23:31I say when your array has one element
23:35when your array has one element so if I
23:37have to index it can I say this is index
23:40zero this is index one this is index 3 2
23:433 4 5 6 7 8 can I say these are the last
23:49indexes and if I have to ask what array
23:52is this you'll be like this array
23:55is something like from index one to
23:59index one where index one is the low
24:02index one is the high can I say this is
24:04the array that represents this yes
24:07because we are not creating a new array
24:09I am saying this array is from index one
24:12to index one which is this right so can
24:15I say the moment we have the low the
24:18left point we have the high the right
24:20point to be same that's when we do not
24:23go and divide we do not divide we just
24:26go back so that's what the base case
24:28will be we write he if at any moment the
24:34low tends to be equal to equal to high
24:38or exceeds high for that reason or maybe
24:41it's some how like it will never but
24:44still this for safety reasons if it
24:46exceeds High please do not because
24:48there's no need to do any of the further
24:50algorithms it's a single element array
24:53and it will always be sorted please go
24:55back please go back so this is how the
24:57pseudo code will look like might seem a
25:00bit confusing but now when I'll dry run
25:02by taking an example it straight away
25:04get to your head okay so we can see that
25:06the pseudo code has been completed but
25:09in order to understand this algorithm
25:11with Clarity we have to do a dryon of
25:13this recursive algorithm then only it
25:15will get clarified so let's try to do a
25:19dryon by taking this particular example
25:23so remember one thing whenever this
25:25algorithm is called it is called with
25:27the complete AR AR so the entire array
25:29is always been passed with this
25:31algorithm and the initial low and high
25:33will be 0 and four because that's what
25:36for this particular example it will be
25:37because initially I will pass on this
25:40entire array and ask mot to sort it so
25:43what will happen will this first base
25:45case operate because no low is still
25:48smaller than high so it doesn't mid
25:51comes out what will be the value of mid
25:54can I say the value of mid will be two
25:56so what happens is it goes goes ahead
25:58and calls the M shot it goes ahead and
26:01calls the mer shot so let's copy paste
26:04the same algorithm let's do
26:07it so I've copy
26:09pasted so what we can say is this
26:12particular recursion call will call this
26:14particular function again but this time
26:17it will pass the low as zero and pass
26:19the high as two so apparently what
26:21happens is it calls for this guy
26:25remember how recursion works is first
26:27this will get oper ated comes back then
26:30this line gets operated that's how
26:32recursion works so that's why first the
26:34left portion will get operated so the
26:37recursion call for zero to goes now what
26:39happens does this line operate no this
26:41line doesn't operates what happens tries
26:44to find the mid and this time the mid
26:46comes out to be 1 because 0 + 2 is 2 and
26:512 by2 is one so one comes out so this
26:54time again this SM shot gets called but
26:57if the M shot gets called called what
26:59will happen it gets called For What from
27:020 to 1 so it's like 3 to 2 is what it is
27:05getting called and then it will be
27:06called for the only number four which is
27:09just two so we will go ahead and maybe
27:12again call this recursion let's go ahead
27:15and call the recursion again so the
27:17recursion is again called what happens
27:19this time the mot is called with 01
27:22which means this particular example
27:25right so this time the lower is 0 the
27:28high is one so what happens the mid is 0
27:31+ 1 by 2 which is nothing but Zer so
27:35again the M shot is called so let's
27:38again copy paste this same
27:41algorithm the M shot this time is called
27:44for 0 0 if I go into the diagram it's
27:47something like for three and something
27:50like for just one so this time it's
27:52called for three so what happens is it's
27:55called for 0 and zero so apparently this
27:58particular base case gets executed and
28:01it returns so I can say the it's done
28:04it's done so if I have to go back into
28:07the chart this goes back similarly
28:11another more shot will be called let's
28:15try to write this as
28:16well and this time it will be called for
28:19from mid + one to high so mid was zero
28:23so it'll be like 1 comma 1 because high
28:26was one mid was was zero so bit + 1 is 1
28:30high is 1 so high is 1 it's called for
28:331A 1 again the low the base case
28:36operates and it calls back apparently
28:40both of these recursive functions are
28:43completed once both of these recursion
28:45functions are completed can I say this
28:49that I'm going back from here and now we
28:52have this as sorted we have this as
28:53sorted it's two sorted arrays it's two
28:56sorted arrays what will happen happen
28:58let's go back here this merge happens so
29:01it takes a three it takes a two and it
29:05tries to merge it now we will write the
29:07merge algorithm afterwards but let's
29:09understand just imagine merges merging
29:12two arrays that's it that's a very
29:13simple algorithm just understand this so
29:152A 3 happens so what would have happened
29:182A 3 right so this would have become 2
29:22comma 3 perfect let's go back to the
29:25recursion so can I say now we can go
29:29back from here to here and we can say
29:31the 01 is sorted so this time this
29:36recursion will again be called let's try
29:38to write it so what will be this
29:40recursion if 01 is done sorry my bad if
29:4501 is done what's the next mid + 1
29:49that's two I is two so you'll call it
29:51for 2 comma 2 and if you call it for 2
29:54comma 2 what will happen yes they are
29:56the same numbers so it will will return
29:59and if it returns this time what will
30:01happen it called for 2 comma 2 this guy
30:06has done the recursion and this guy has
30:08done the recursion so apparently again
30:11the merge happens this time the merge
30:13happens from 0 to 1 till the two the
30:17merge this time happens for 2 comma 3
30:20and maybe four or whatever it
30:23is yes and this will become 2 comma 3A 4
30:27I hope you getting the gist so can I say
30:30after this I'll again go back and when I
30:34go back now I'll try to just come back
30:37yes when I go back can I see this that 0
30:40comma 2 would have been sorted and if 0a
30:432 is sorted I'm done with this I'll go
30:46to the right part which is having this
30:48and
30:50similarly this is done so this will call
30:53it right and how will it call it let's
30:57copy paste and show it
30:58if 0a 2 has been done so can I say next
31:02is mid + 1 so this is nothing but three
31:05highest four this time it goes and calls
31:07for 3 comma 4 again the same thing will
31:10happen the mid will be like 3 + 4 7 by
31:1423 so it will be called for 3 comma 3
31:17and then it'll come back this will be
31:19called for 4 comma 4 it'll be come back
31:22and then this will merge both of these
31:25two elements it's like it'll be called
31:27for one it'll be called for three then
31:29they will be merged as 1 three and once
31:33this is done what do we have we have 0a
31:362 sorted we have 3A 4 sorted so the last
31:40merge takes place between this 0a 2 that
31:44is 2A 3A 4 and 1A 3 so apparently they
31:48are merged together when merged you'll
31:52get 1 2 3 3 4 that is what happens at
31:55the last step I hope that
31:58does make sense so so I hope the dry run
32:01is clear in terms of the pseudo code it
32:03was very simple first the entire array
32:06goes to the left goes to the left goes
32:08to the left goes to the left and then
32:10merges it always performs this recursion
32:13first this recursion first this
32:15recursion first once this is completed
32:18then this once both are completed then
32:20the merge happens need to understand
32:23that this is how the flow Works in order
32:24to understand this in much more depth
32:27what I'll recommend you is take a pen
32:29and paper write this code try doing it
32:32all over again got it so what have we
32:35completed we have completed the dryon
32:38the pseudo code as well but before going
32:40into the code we still are left with the
32:43merge pseudo code if we are able to
32:45write the merge pseudo code I think we
32:47will be done so let's take a bigger
32:50example in order to understand the merch
32:52pseudo code can I say the indexing is
32:54like 0 1 2 3 4 5 6 7 7 8 and this is
32:58like 0 1 2 3 4 and this is like 5 6 7
33:02and 8 and if the merch will happen I
33:06will call it like merge these two arrays
33:09because if you know this array when goes
33:12into depth goes into depth it will be
33:14sorted it'll be sorted like 1 1 2 3 4
33:18and this also will go into the depth and
33:20it will be sorted like 24 56 this is
33:23something which all of us know for sure
33:25that both of them will be sorted and and
33:28both of the array will be something like
33:301 1 2 3 4 and this will be like 2 4 5 6
33:34this is something we know and this will
33:37be index from 0 to 4 this will be from 5
33:40to 8 that's something we know we just
33:42have to write an algorithm to do it
33:45so we're writing the algorithm okay so
33:47we're saying
33:51merge I'll give you the array and I'm
33:53stating you that the first half is from
33:56low to mid and then you can go from mid
33:59plus one to high so I'm giving you all
34:00the three parameters
34:02required what I'll do is maybe I'll just
34:05keep an empty data structure it can be a
34:08vector it can be a list as of now just
34:11imagine this is an empty data structure
34:14where we can add elements okay now can I
34:18say that the left array will be from low
34:22to mid and can I say the right array
34:25will be from mid plus one to high I I
34:27can so I will keep couple of pointers so
34:31I'll say okay left pointer is at the low
34:36so that means left comes over here and
34:38I'll say right pointer is nothing but at
34:41Mid + one so what happened I'll say WR
34:44is here now what will I do I will try to
34:48compare these two and try to fill in
34:51this bigger array the bigger array I'll
34:54try to compare these two and try to fill
34:56in the bigger array so what I will do is
34:59I will now try to iterate till what till
35:02we have elements on the left or till we
35:04have elements on the right can I say
35:07that means I will say while left is
35:10smaller than equal to Mid which means I
35:14still have element and I'll say and and
35:18right is lesser than equal to high which
35:21means I still have elements on the right
35:25very simple now what I'll do is
35:28okay this is what I'll do till I have
35:29elements on the left till I have
35:31elements on the left on the right so
35:34I'll not try to compare I will say Hey
35:36listen if array of
35:38left is smaller than equal to array of
35:42right so what
35:44happens this and this gets compared and
35:48if one is smaller than two I'll take one
35:51and I'll add it to our resultant guy
35:54I'll add it to our resultant guy so I'll
35:56say okay maybe uh we can name this as
35:59something
36:01else let's go and name this as maybe
36:03let's say temporary that's a better name
36:06as a temporary can you please add
36:08yourself the smaller guy array of left
36:11and once you have done this can you move
36:13ahead the pointer which means the left
36:16pointer goes to the next again so
36:19basically what will happen is now
36:21temporary will have one with itself
36:24again the comparison between one and two
36:26will happen and this one will come here
36:28the temporary again takes it and now the
36:30left moves here again the comparison
36:33between two and two will happen and it
36:35comes here and the left moves here this
36:37time when you compare three and two when
36:40you compare three and two the two will
36:42come but the if only Compares for lesser
36:45so there will be a else so else will
36:47state can you please add the right guy
36:51can you please add the right guy that is
36:53take from the array and add the right
36:56guy and once you have added can you move
36:59the right Plus+ so what I'll do is I'll
37:01move the right to ahead now that's how
37:06this will work and you'll keep on
37:07comparing and you'll keep on adding till
37:10this is not completed so what will
37:12happen this two will come and the right
37:14will move here now the comparison
37:16between four and three happens so three
37:19comes and the left moves here now four
37:22comes and the left is exhausted left
37:25exceeds mid left exceeds mid so we see
37:28that the left has exceeded mid there is
37:30no one on the left so what I will say is
37:33after the end if there
37:35is anyone on the left which means if
37:38there is anyone on the left because if
37:42this while if this while loop is false
37:44either it will be false because this is
37:46true or this is true so if there are on
37:50the left if there are on the left I will
37:53still add it I just take everyone from
37:56the left and add it to my
38:01stuff and if there are people on the
38:04right because anyone will be true either
38:08there will be on the left either there
38:10will be on the right if there are people
38:12on the
38:13right which will be right high and then
38:18I'll say temporary do add array of
38:22right and I'll do right Plus+ quite
38:25simple
38:27if that means if on left copy them if on
38:32right copy them as simple as that so can
38:36I say at the end of the day I would have
38:38four 4 5 six all of them in the
38:41temporary area now we need to place them
38:44into the original array so what have we
38:46completed till this step we can say the
38:50left sorted array and the right sorted
38:52array have been put into a third array
38:55temporary but we actually need to put it
38:59from low to high because that's the
39:01original array because the original
39:03array is from 0 to 8 and you take these
39:05elements and put it there because it is
39:08in temporary so what I'll do is I will
39:11probably Loop yes let's Loop I'll say
39:13for I from low to high is where I Loop
39:17please loop from there and I'll say
39:19array of I that means who is the first
39:22element
39:24temporary temporary must be keeping
39:27because it's a temporary array it will
39:29always keep in the zero index so I'll
39:31always say
39:33temporary I minus
39:36low that's it first time I will be low
39:39so what will this happen low minus low
39:42that will be zero next time I will be
39:44low + one so low + 1 minus low that'll
39:47be one next time I will be low plus 2
39:49low plus 2 minus low that'll be two so
39:51it will get all these indexes because it
39:55will be stored in a temporary array
39:56it'll pick up all these indexes and
39:59store in the correct order so it'll pick
40:02up all these indexes at 0 1 2 and store
40:06it in the correct order from low to high
40:08because
40:10because this was low to mid this was mid
40:13plus one to high and they CAU together
40:15from low to high that was the original
40:17array got it this is how the merge will
40:21look like I hope that does make sense so
40:23now I can confidently say that You' have
40:25understood the explanation the pseudo
40:27code and the dryon so you can code it in
40:29C++ Java and python so I'll just go
40:32across and code it in C++ but the Java
40:35and python codes you can find them in
40:37the links in the description it will be
40:39updated very very soon just in case it
40:41is not there as of now let's come to the
40:42compiler and try to code it so we have
40:44given a function we given the array and
40:46we given this so assume we are going to
40:48write this function and we say void uh M
40:52short and I'll say let's take the array
40:55which is this please make sure you pass
40:57it reference low and high that's what we
41:00require and we know one thing if low is
41:02equal to equal to high we're going to
41:04return that's it otherwise we are going
41:06to find a middle which is low plus High
41:11by 2 and then we will be calling the MS
41:14with array comma low comma mid and
41:20Ms aray comma mid + one comma high and
41:24then we will be calling something like
41:26merge Where will passing array low mid
41:30and high that's what the algorithm will
41:32be and we can call Ms with the array and
41:360 comma n minus one because that's the
41:38initial starting and the end position of
41:41the entire array just have to write the
41:43merge function and I think we will be
41:45done so let's write the void merge and
41:48again make sure you take everything by
41:50reference array and then low and then
41:53you can take mid and then you can take
41:55High
41:58so can I just take a temporary array we
42:01can and we can take the left pointer to
42:03be low plus one uh sorry low rather and
42:06we can take the right pointer to be mid
42:08+ one because we know the first array
42:10will be like if I have to commented it
42:13will be from low to mid and the second
42:15array if you remember it will be mid +
42:17one till high so let's see uh let's
42:22write this so we say left is lesser than
42:24equal to Mid and and M and and
42:29write is lesser than equal to high very
42:33simple but we need a temporary array
42:36that is defined over here we say hey
42:38array of left are
42:41you smaller than array of right if you
42:45are can you please go ahead and get
42:48attached push
42:51back to array of left very simple at the
42:55same time we can do a left Plus plus and
42:58you can write an else and you can
42:59temporary do push back array of right
43:04and you can say right Plus+ this is what
43:07you will do for comparing and putting it
43:09after that if there are still elements
43:12left on the left please take it because
43:14if this is false then this must be
43:17having some elements on the left so go
43:19ahead and just copy paste this
43:23perfect and if there are still elements
43:26on the right then go ahead and copy
43:29paste everything from the right quite
43:32simple once you have done this make sure
43:34you put them into the array which is for
43:36in I equal to low I less than equal
43:40to high and I ++ and you can say array
43:44of I will be temporary of I minus low so
43:49once you've done this since everything
43:50is by reference the the numbers will
43:53rearrange themselves in the array itself
43:55now I can go ahead I can go ahead and
43:57run this and see if it is running fine I
43:59hope it does it does and now I'll
44:01quickly submit this I write codes in one
44:05go W nice no syntax errors so we have
44:09understood everything but there's only
44:12one thing that is left which is the time
44:15complexity of this merge short algorithm
44:18remember one thing what's happening
44:21there's an N size array which is getting
44:23divided to n by2 n by2 then this n by2
44:26is getting divided to n by4 n by4 n by4
44:30and n by4 so at every step they're
44:34getting divided by two by two by two by
44:37two and if you remember the time
44:39complexity lecture I have already told
44:42whenever it gets divided by by two the
44:45time complexity is log base to n
44:47remember this now you might ask me but D
44:50why you're dividing it by by 2 by 2 but
44:53why it is log base 10 it's very simple
44:55if I have to write 16
44:57and I have to divide it by two it'll be
44:59like 8 and 8 it'll be like four and four
45:04right like if there are four like if
45:06there are 16 array elements gets divided
45:08into 8 and8 eight gets divided into four
45:10and four four gets into two and two and
45:12then two gets into one and one so
45:15apparently this is nothing but one step
45:19two step three step four step and 16 is
45:23nothing but 2 to the^ 4 and that's
45:27nothing but four steps right four steps
45:30log base 26 is nothing but four steps so
45:33it's approximately logarithmic number of
45:37times the division happens it's
45:39approximately logarithmic number of
45:41times that the division happens that
45:43means it gets broken down into
45:46logarithmic of end time and you're also
45:49performing something like a merge every
45:53time so every time division by like this
45:56is div this is half and this is half
46:00this half Will Go On Till log base 2 N
46:04near about again everything is in terms
46:06of nearabout okay time complexities goes
46:09till near about log base 2 and then
46:11there is a merge happening how much is
46:13merge taking if I have to think of the
46:16extremest case if I have to think of the
46:19extremest case can I say this is of size
46:21three this is of size two so in order to
46:25merge three and two elements
46:27I'm going to require five steps at
46:30minimum one comparison that's like
46:32everyone is comparing in itself it's
46:34like a near about B go of n that's the
46:38worst case because for this I'll end up
46:40taking at minimum of five steps because
46:44every element is compared one by one and
46:46then it is put over here it takes
46:48minimum of five steps which is nothing
46:50but the length of the array at the worst
46:52case so can I say the merge I have to go
46:57back to this uh there's so many things
46:59written man I have to go back this can I
47:01say this at the worst case takes B of n
47:04this time over here it might take B of n
47:07by two over here it might take n by4
47:09something like this but at the worst
47:11case it is taking n thereby I can
47:14actually say that the time complexity is
47:17nothing but n into log base 2 N now you
47:22might ask me qu a question but St wait
47:26once step two step three step four step
47:28who will be counting these steps wait
47:32that is actually compensated
47:34how because the merge over here takes
47:38big of n the merge over here takes n by2
47:41the merge over here will take n by4 the
47:42merge is taking lesser so in overall if
47:46you try to add it up in mathematical you
47:48will actually get somewhere near about n
47:52into log base 2 N as the mer shorts time
47:56complex so n log is the best average and
47:59the worst case but if I have to ask hey
48:02what is the space complexity of the
48:03algorithm how much extra space are we
48:05using so if you remember the algorithm
48:08the algorithm is actually using indexes
48:11no separate Ares is this the given array
48:13that they are using are they using any
48:15extra additional space they are during
48:17merge in every merge step they're
48:20creating a temporary array which at the
48:22worst case might take B of in so the
48:25space complexity at the worst case is
48:28beo of n near about beo of n for this
48:32particular algorithm so with this I will
48:34be completing M short and the time is uh
48:373:28 a.m. in the morning as you can see
48:40I cannot record in the day because
48:41there's a lot of background noise so
48:44just in case you understood everything
48:46please please consider hitting that like
48:48button and if you haven't checked out
48:50sters a to DSA course the link will be
48:52in the description please make sure to
48:54check it out because we have notes for
48:56every everything we will be attaching
48:58video solutions to everything yes most
49:01of the advanced topics have been covered
49:03previously I'm starting to cover the
49:05basic topics now so you can definitely
49:07proceed ahead with the advanced topics
49:09in case you need for Advance as well so
49:11guys if you're new to our Channel please
49:12do consider hitting that subscribe
49:14button because that is the only thing
49:15that keeps you motivated to make these
49:17kind of videos and and yeah to follow
49:19our tradition please make sure you
49:20comment understood in the comments so
49:22that I get a VI that you guys are
49:24understanding everything so with this
49:25I'll be wrapping up this video if you
49:27haven't followed me on Instagram Twitter
49:28LinkedIn the links will be in the
49:30description with this let's wrap up this
49:31video and meet in some other video till
49:33then
49:33byebye your heart is
49:37broken your
49:39golden I will

About this transcript

This page contains the full transcript of Merge Sort | Algorithm | Pseudocode | Dry Run | Code | Strivers A2Z DSA Course by take U forward, generated from the public captions YouTube serves with the video. The transcript has 8,560 words across 1,087 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.