How Merge Sort Works?? Full explanation with example

How Merge Sort Works?? Full explanation with example

How Merge Sort Works?? Full explanation with example

👉Subscribe to our new channel:   / @varunainashots  

👉Links for DAA Notes:

đź”—File-1: https://rb.gy/2byrg
🧑‍🎓Contributed by: Junaid Gazi

đź”—File-2: https://rb.gy/gibu5
🧑‍🎓Contributed by: Mannu Garg

The “Merge Sort” uses a recursive algorithm to achieve its results. The divide-and-conquer algorithm breaks down a big problem into smaller, more manageable pieces that look similar to the initial problem. It then solves these subproblems recursively and puts their solutions together to solve the original problem.

â–şDesign and Analysis of algorithms (DAA) (Complete Playlist):
   • Design and Analysis of algorithms (DAA)  

Other subject-wise playlist Links:
--------------------------------------------------------------------------------------------------------------------------------------
â–ş Operating System :
   • Operating System (Complete Playlist)  
â–şDatabase Management System:
   • DBMS (Database Management system) Com…  
â–ş Theory of Computation
   • TOC(Theory of Computation)  
â–şArtificial Intelligence:
   • Artificial Intelligence (Complete Pla…  
â–şComputer Networks (Complete Playlist):
   • Computer Networks (Complete Playlist)  
â–şComputer Architecture (Complete Playlist):
   • Computer Organization and Architectur…  
â–şStructured Query Language (SQL):
   • Structured Query Language (SQL)  
â–şDiscrete Mathematics:
   • Discrete Mathematics  
â–şCompiler Design:
   • Compiler Design (Complete Playlist)  
â–şNumber System:
   • Number system  
â–şCloud Computing \u0026 BIG Data:
   • Cloud Computing \u0026 BIG Data  
â–şSoftware Engineering:
   • Software Engineering  
â–şData Structure:
   • Data Structure  
â–şGraph Theory:
   • Graph Theory  
â–şProgramming in C:
   • C Programming  
â–şDigital Logic:
   • Digital Logic(Complete Playlist)  

---------------------------------------------------------------------------------------------------------------------------------------
Our social media Links:
► Subscribe to us on YouTube:    / gatesmashers  
►Subscribe to our new channel:    / @varunainashots  
â–ş Like our page on Facebook: https://www.facebook.com/gatesmashers
â–ş Follow us on Instagram: https://www.instagram.com/gate.smashers
â–ş Follow us on Instagram: https://www.instagram.com/varunainashots
â–ş Follow us on Telegram: https://t.me/gatesmashersofficial
â–ş Follow us on Threads: https://www.threads.net/@gate.smashers
--------------------------------------------------------------------------------------------------------------------------------------
â–şFor Any Query, Suggestion or notes contribution:
Email us at: gatesmashers2018@gmail.com


Content

0 -> Dear students, welcome to Great Smashers
2.02 -> In today's video I am going to explain working of Merge Sort
5.24 -> How does Merge Sort work?
7.26 -> How does it work?
9.28 -> We will see that in this video
10.8 -> In the next video we will discuss its pseudo code
14.02 -> And also check the time complexity and space complexity
18.04 -> So guys, it is very important to check all these videos properly
21.26 -> And tell you one thing
22.78 -> The most important point of the first Merge Sort is
25.3 -> That it is a divide and conquer strategy
27.5 -> And I have already told you what is divide and conquer
30.52 -> Which algorithms and techniques are used
33.34 -> So Merge Sort is also a part of divide and conquer
36.06 -> The second most important part is
38.08 -> That I have already discussed a lot of sorting algorithms
42.6 -> I have already told you quick sort, insertion sort, bubble sort
45.42 -> I have already covered all these
47.62 -> But if we talk about Merge Sort
50.24 -> Then its biggest advantage is
52.76 -> That its time complexity is n log n
56.16 -> What is its time complexity?
57.879 -> n log n
59.4 -> Whether you talk about any Merge case
62.22 -> Whether you talk about best case
64.14 -> Whether you talk about average case
65.96 -> Whether you talk about worst case
67.88 -> It will be on n log n
69.6 -> Okay, so remember these main points
71.62 -> I will explain all of them one by one
73.64 -> But first of all see the working
75.56 -> Because this is the most important part of Merge Sort
78.679 -> So see, I have taken an array here
80.9 -> It has 8 elements in it
82.52 -> So let's say my index number 1, 2, 3, 4
86.02 -> 5, 6, 7, 8
88.24 -> So I have 8 elements in the array
90.66 -> And the first thing we have to do is
92.979 -> as it is dividing and conquering, first divide
95.6 -> Means what is my problem? Big
97.58 -> What is this big problem?
99.22 -> We have to sort this array
100.94 -> So what do you say first? Divide
102.96 -> Means divide your problem into sub problems
106.08 -> And bring it at the stage when only one element is left in the array
111 -> Means bring it to the termination
112.82 -> This is the first condition
114.02 -> So what we have to do is there are 8 elements
116.039 -> So obviously what I will do first is
117.56 -> I will break it into two equal parts
119.88 -> So what I have in the first part
121.899 -> 4 elements are there
123.22 -> 6, 4, 2 and 1
126.539 -> Okay, and the second one is here
128.16 -> Again 4 elements are there in all the arrays
130.579 -> 9, 8, 3, 5
134 -> Now if you are thinking that
135.72 -> Sir you have divided 8 elements in 4, 4
139.22 -> It's a very easy job
140.44 -> If total were 9 elements
142.44 -> So no problem, if there were 9 elements
144.46 -> Then in the first one 5 would have come
145.98 -> In the second 4 would have come
147 -> There is no problem
148.02 -> But you have to see its working first
150.04 -> We will see all those things further
152.26 -> So see its working here
153.78 -> So first divide the big array into two small sub-arrays
157.8 -> There were 8 elements, so 4 came in it
159.82 -> 4 came in it
160.84 -> So the big problem will be divided into two sub-problems
162.86 -> Now this sub-problem
164.88 -> We will divide it further
166.4 -> We will divide it separately
168.12 -> So in a way recursion works here
170.14 -> Recursion
171.14 -> In the first recursion 8 became 4, 4 into 2 pieces
174.16 -> Now in the next recursion
176.179 -> This 4 problem will be broken into two pieces
179.22 -> 6 and 4
180.239 -> And in the second piece 2 and 1 came
183.192 -> Okay
184.217 -> This sub-problem again we have
186.299 -> Obviously as we broke this, we will also break this
188.32 -> So we have divided this too
190.339 -> So 9 and 8 came here
191.859 -> And 3 and 5 came here
194.88 -> Okay
195.899 -> So my problem is dividing into sub-problems
198.9 -> But till then we have to do it until there is only one element left in the array
202.92 -> Means the termination condition
204.94 -> So here again we will break it again
206.96 -> So 6 came here, 4 came here
208.98 -> Here 2 came here
210.5 -> Here 1 came here
212.02 -> Okay
212.54 -> Here your 9 came here
214.06 -> Here your 8 came here
216.08 -> Here your 3 came here
217.6 -> And here what came here
219.12 -> 5 came here
220.14 -> Okay
220.66 -> Your problem was in the sub-problem
222.68 -> You can say that until there is only one element in the array
227.68 -> Till then we have to divide it
230.7 -> Recursively it will work
233.22 -> When there is only one element left in your array
235.24 -> Means you can't divide further than this
237.76 -> Now what to do with this?
239.28 -> Merge it
240.3 -> Means divide and conquer
242.32 -> Now you will have a conquer stage
244.34 -> Which?
245.36 -> Conquer stage which we can also call merge
248.38 -> Okay
249.4 -> So what to do to merge?
250.42 -> I write it up so that you get full clarity
252.94 -> It works in this way
254.792 -> So see first of all we had 6 here
257.658 -> Here we had 4
259.683 -> After 4 we have 2 here
261.708 -> Then we have 1
263.02 -> Then we have 9
265.039 -> Then we have 8
267.06 -> After that we have 3
269.08 -> And finally we have 5
271.099 -> Okay
271.62 -> So this was our sub-problem
273.14 -> It was divided like this
274.659 -> Now what we have to do is conquer or merge
276.679 -> So what to do to merge?
278.2 -> Same thing
279.219 -> Now what we have to do is
280.24 -> First divide it into pieces
281.76 -> Now divide it into two and keep joining them
283.78 -> What to do with these two?
285.299 -> Keep merging
286.3 -> And while merging what to keep in mind?
288.32 -> You will keep on sorting elements
290.34 -> Like if you merge 6 and 4
292.36 -> Then what will it become?
293.38 -> 4, 6
294.825 -> Okay, means it is sorted
295.92 -> Okay
296.94 -> Merged 6 and 4
297.96 -> So sort it together
299.98 -> Here we did 2 and 1
302 -> So what did it become?
303.02 -> 1 and here 2 came
305.04 -> Okay
306.06 -> Here we did these two
307.08 -> So this is 8 and here 9 came
310.1 -> Here we did these two
311.12 -> So it was already sorted
313.14 -> No problem
314.16 -> As it is write it
315.16 -> Sometimes it happens that it is already there
316.98 -> So this is your as it is
318 -> Now what to do?
319.02 -> Now what to do with these two?
321.04 -> Merge
322.06 -> What to do with these two?
323.08 -> Merge
324.1 -> So to merge these two
325.12 -> I give you a little idea
326.14 -> How we actually did it?
327.66 -> Let's say this is my array L
330.185 -> This is my array R
332.009 -> Okay
332.542 -> So this is the first element of L
334.365 -> This is the second element of L
335.39 -> This is the first element of R
336.601 -> This is the second element of R
337.626 -> Like this
338.651 -> So what we did here
340.34 -> We took a pointer I
341.84 -> Here we took a pointer J in R
344.34 -> Means L.I is the first element
346.359 -> R.H is the first element of this
349.362 -> Now we have to compare these two
350.962 -> We have to compare L.I with R.J
353.917 -> So which element is smaller than I and J?
357.228 -> Write down whatever is smaller than that first
360.46 -> Which element is smaller than these two?
362.973 -> R.J element
363.998 -> 1 is smaller
364.998 -> So we wrote 1 here
366.532 -> We wrote 1 here
367.885 -> This 4 was big
368.91 -> Which is bigger than 4 and 1?
370.099 -> 4
370.757 -> Which is smaller than 1?
371.777 -> So we wrote 1 here
373.14 -> Remove this in a way
374.659 -> And move J ahead
376.68 -> It's simple
377.7 -> Write down whatever was smaller in the next one
380.219 -> And moved J ahead
381.74 -> If it was smaller here
383.159 -> Then we write this here
384.18 -> And move I here
385.7 -> See we moved J here
387.219 -> J came on this
388.24 -> Came on 2 here
389.76 -> Now compare 4 and 2
391.28 -> I is still there
392.3 -> We compared 4 and 2
393.82 -> Which is smaller?
394.84 -> 2 is smaller
395.86 -> So we wrote 2 here
396.88 -> Now moved J ahead
398.9 -> Now there is no element ahead of J
400.919 -> So what we do here is
402.42 -> Add infinity to it
404.24 -> Means we add a big element
407.054 -> So that your comparison keeps going
408.78 -> Why did we add big element?
410.3 -> So that your comparison doesn't stop
411.82 -> Now see after this comparison doesn't stop
413.84 -> So how do you move ahead?
415.36 -> You can't move ahead
416.38 -> So we put infinity here
417.9 -> Now see 4 and J is infinity here
420.92 -> So which is smaller than 4 and infinity?
423.94 -> 4 is a small element
425.96 -> So 4 is as it is ahead
427.48 -> Okay?
428.034 -> Now if you want to move ahead
430.5 -> But you know if you compare it with infinity
433.02 -> Then obviously that element will be smaller
436.04 -> Infinity is very big
437.06 -> So obviously 6 is as it is written here
440.08 -> Okay?
440.827 -> So it works like this
443.115 -> Next we have to put the same thing here
445.64 -> To put it here
447.291 -> It means I is here and J is here
449.224 -> Now see we will do the same thing
450.7 -> Here 4 elements will come
452.22 -> Which is smaller between I and J?
453.74 -> Between I and J
454.76 -> This 3 is smaller than you
456.78 -> So we did this
457.8 -> We moved it ahead
459.3 -> Here 5 came here
460.82 -> And then 8 and 9 will keep on increasing like this
463.84 -> Then finally what we have to do with these two?
466.36 -> We have to merge them
467.38 -> So to merge these two then we...
469.9 -> 3, 4, 5, 6, 7
472.92 -> 5, 6, 7 and here comes your 8
476.284 -> Okay?
476.96 -> Now see this is my I here
478.98 -> And J is here
480.5 -> Okay?
481.02 -> I is here and J is here
482.54 -> This is L
483.56 -> This is R
484.58 -> Now see L.I and this is comparing R.J
487.6 -> So which element is smaller?
489.1 -> This is smaller
490.12 -> I is smaller
491.14 -> So we wrote 1 here
492.66 -> We moved 1 here
494.18 -> We incremented I
495.7 -> We incremented I
496.72 -> Now I is here
497.74 -> Now see between 2 and 3
499.26 -> J is still there
500.28 -> Which is smaller between 2 and 3?
502.3 -> 2 is smaller so we wrote 2 here
504.32 -> And move it here
506.34 -> And this is your I moved
508.36 -> Okay?
508.88 -> Means there is no need to move it
510.4 -> You can just...
511.42 -> So that you don't have any confusion in your mind
513.94 -> So move I ahead
515.46 -> Now your I is here
516.98 -> Now see which is smaller between I and J?
518.98 -> J is smaller now
520.8 -> So move it here and move it ahead
523.32 -> Now see I was here
525.34 -> And J is here
526.86 -> So which is smaller between 4 and 5?
528.88 -> This is your 4 is smaller
530.9 -> So move 4 from here
532.92 -> And bring I to 6
534.44 -> Now see which is smaller between 6 and 5?
536.46 -> 5 is smaller
537.48 -> So move it ahead
539.5 -> And comparing between 6 and 8
541.52 -> So 6 is smaller
544.04 -> And this is your infinity ahead
546.06 -> Same thing
547.08 -> It went to infinity
548.08 -> I went to infinity
549.6 -> Now you don't have to compare
551.62 -> Because one side is infinity
553.64 -> And other side is 8
554.66 -> So obviously write 8 as it is here
558.18 -> And write 9 as it is here
560.7 -> You don't have to do anything to 9
562.72 -> When you know from 8 as infinity
565.74 -> One side is infinity
567.76 -> So write all the other elements as it is here
570.78 -> So here your array is sorted
573.8 -> So this was the whole portion divide
575.8 -> And this was the whole portion conquer
578.62 -> So this is how divide and conquer
580.64 -> Or you can say merge sort
582.66 -> works like this
584.18 -> So in the next video I will show you
586.199 -> I will compare it with its pseudo code
588.224 -> and show how it actually works.

Source: https://www.youtube.com/watch?v=tn9hxD8gx2M