• 2 days ago
Transcript
00:00First of all, the question we are solving is Merge Sort
00:03We have studied a lot of basic sorting algorithms
00:05We have studied our bubble sort
00:10After that, we have studied selection sort
00:13After that, we have studied insertion sort
00:14After that, we have studied counting sort
00:18We have also studied an inbuilt sort
00:21If I have an array that I have to sort
00:24What can I do?
00:25I can use a small and simple function
00:29These sortings are in basic sorting
00:31Inbuilt sort and optimized sorting
00:34But today, we will study a different sorting technique
00:38which is called Merge Sort
00:39Merge Sort
00:42Merge Sort
00:42The logic behind it is very important
00:44which is also used in other problems
00:46The process of divide and conquer
00:49is used in many algorithms
00:51Merge Sort
00:52The logic of Merge Sort
00:55can be asked in college
00:57You can also ask in college exams
00:59and you can also ask in some companies to implement it
01:00You can also ask directly questions
01:02So, Merge Sort
01:04Merge Sort
01:05Merge Sort
01:29Merge Sort
01:32Merge Sort
01:33In fact, there are other orders
01:34but we will assume that in ascending and descending order
01:37we will sort our elements
01:39So, what will it be for us?
01:41Today, we are taking an example of ascending
01:44We will give an unsorted array
01:46We will give an unsorted array
01:46which is stored in some random way
01:48in which elements are stored
01:49That means
01:506, 3, 9, 5, 2, 8
01:52We have to convert this unsorted array
01:54in this sorted array
01:57And all the elements
01:59in the sorted array
02:00are arranged in ascending order
02:02Now, we have ascending order
02:14which we have to follow
02:14So, what will it be?
02:17The first step in the approach
02:19is to divide
02:21That means
02:22we have to divide
02:22our problems
02:24and divide
02:25within small problems
02:26What will it be?
02:28We will remove our array
02:29mid
02:30If I have this array
02:32then what will it be?
02:34I can take this index
02:35or I can take this index
02:37So, if my starting index is 0
02:40and my ending index is
02:41length minus 1
02:43which is 0, 1, 2, 3, 4, 5
02:45So, my ending index is 5
02:47So, for this array
02:48I have the middle index
02:50I can select both of them
02:52Let's say
02:53I have selected the middle index
02:54for my array
02:56which is this index
02:57That means
02:58I want to partition my array
03:00So, my problem will divide
03:02in two parts
03:03Which part will be?
03:05One will be my left part
03:06What will it be?
03:08What will it be?
03:08I don't want to sort the large array
03:10Now, I have to sort the 6, 3 and 9
03:13And the other will be my right part
03:15What will it be?
03:16What will it be?
03:16I don't want to sort the large array
03:18I have to sort the large array
03:21I have to sort the small array
03:22So, what do I do?
03:23I have divided my big problem
03:24I have divided in two parts
03:26How did I divide it?
03:27First, I found the middle of my array
03:30Then, I have partitioned here
03:33Partition
03:33Partition
03:33I have to divide it
03:33Or divide it
03:34In two parts
03:36Now, I will divide this array
03:37In small parts
03:39And when will I divide it?
03:41Until I get the smallest problem
03:42Or the easiest problem
03:44To solve the problem
03:45Like
03:46If I have to sort these three
03:48Numbers
03:49Arrays
03:50What will I do?
03:51I will find the middle
03:52What will it be?
03:55What will it be?
04:04The middle problem
04:05This problem
04:05May be the two parts
04:06One will divide it
04:07One will be my left
04:08What will it be?
04:09The left
04:09What will it be?
04:10Don't do large powers
04:12You only fill the space
04:13Six to three
04:13You only fill the space
04:15The one will be my right
04:17What will it be?
04:18The one will do
04:18The left
04:19The left
04:30The left
04:31The left
04:33I divide the problem to 5 and 2 and divide the problem to this single 8.
04:39Now what I can say is that I can't divide this problem.
04:43Because if there is a single element in an array,
04:46then it is not already sorted.
04:48It is not already sorted.
04:50So this part is already sorted.
04:54This part is already sorted.
04:58I have to solve this small problem.
04:59I have to solve this small problem.
05:02So what will I do for this small problem?
05:04I will make it smaller.
05:05I will make it smaller until it is not sorted.
05:08So I will take the middle again.
05:11I will partition it and divide it to a smaller problem.
05:15The smaller problem will be that you will solve only the 6th area.
05:19Now you will sort only the 3th area.
05:22I can do the same thing here.
05:24I will partition it in mid.
05:25I will partition it in mid.
05:26And I will say that now we have to solve the left problem.
05:29So we have to solve only the 5.
05:31And in the right I will only sort 2.
05:35Now do I need to divide these problems further?
05:37No.
05:38Why?
05:38Because I have a small problem in last.
05:41I have single elements.
05:44And what are the single elements?
05:45Already sorted.
05:46So the array will already sorted.
05:50Already sorted.
05:50And this will already be sorted.
05:56What I have done this?
05:58I put my problem in small small chunks and divide it.
06:03Until there will not come to all small chunks.
06:07And as I have a small chunk of these chunks
06:09which has divided in small chunks is already sorted.
06:13First step was to divide the problem into smaller parts.
06:19Now, a different thing I note here is that
06:22if I need to solve every chunk of the Array
06:25I have to solve this problem. If I know starting index and ending index,
06:30I was first known that my starting index is 0 and my ending index is 5.
06:35Can I remove starting index and ending index as middle as I have done?
06:40How do I remove starting and ending as middle?
06:42There are two ways. I will write starting index plus ending index divided by 2.
06:47Or I will write starting index plus ending index minus starting index divided by 2.
06:54I will return the right answer to these two ways.
06:57But I will use this method as well.
07:01We can use it as well. The answer will be right.
07:03But there will be a problem when we have a big array.
07:07What happens in a big array?
07:09Sometimes if I talk about starting index and ending index,
07:13then these two integer values can be increased.
07:15And these values can be increased by the size of total integer.
07:19We have the size of the integer.
07:23So in this case, we have to take large data types.
07:26Or we can use this formula.
07:28This formula, I am talking about basic math.
07:32I am talking about basic math.
07:33I can also convert this formula.
07:37Starting index.
07:37If I divide this, this will be ending index by 2.
07:41Minus starting index by 2.
07:42This value will be ending index by 2.
07:45And if I have added this with this,
07:47then this will be plus starting index by 2.
07:50This is equal to ending index plus starting index by 2.
07:52So this formula and this formula are the same thing.
07:55In this case, I will add 2 big size integer
07:58and I will not overflow with my data types.
08:01So the clarity of clarity came in this step.
08:04First of all, I divide my problems.
08:05When I divide them,
08:07until I don't have the small problems sorted.
08:10And this is the biggest problem sorted.
08:13What can I say?
08:14This is my base case.
08:15What is the base case?
08:17I already know the solution for this case.
08:19I know that if I get a single size area,
08:21then what will I always get a solution?
08:23In this solution, I will not do any work.
08:25I have already sorted area.
08:26Another thing I have analyzed.
08:28If you know the starting index or the ending index,
08:31then I can remove the middle from this formula.
08:34I have covered this in my step 1.
08:37Now let's talk about step 2.
08:39Step 2 says that,
08:40as I have removed my problem,
08:43which was the biggest problem,
08:44I have removed the left portion
08:46and divided the right portion.
08:49What do I do?
08:51Recursively, I have called the left portion
08:53and called it.
08:56If I sort it.
08:57So, what do I do in step 2?
08:59What do I do in my merge sort?
09:01For that,
09:02first I have to sort the left portion.
09:05Then what do I do?
09:07I have to apply the merge sort
09:08on the right portion.
09:10If I take this example,
09:12if I have my array 639528,
09:16then what do I do?
09:18First I have to do it from the middle.
09:21I have to do it from the middle.
09:21From the middle,
09:22I have to do it from the left portion.
09:23which will be 639.
09:27And if I have a right portion,
09:29which will be 528.
09:32Now I have to do it from the merge sort.
09:34Then I have to convert it in sorted way.
09:37So, I have to convert it from 369 to 258.
09:41I have to convert it from 258.
09:42I do not see logic now.
09:43How do I convert it from merge sort.
09:45But I have to take this part in sorted.
09:50And how do I take this part in sorted?
09:52I will take this part in recursion.
09:53I will talk about recursion.
09:56But I will take this part in any way.
10:00And then I will apply step 3.
10:02Step 3 is to merge.
10:04If my left part is sorted and right part is sorted,
10:09I will add a big solution to left and right.
10:11And then I will add a big solution.
10:13How will I make the big solution?
10:16Let's see.
10:17This is my array.
10:18I have divided it in 2 parts.
10:20Step 1 was to divide.
10:22What did I do in step 2?
10:23In step 2, I have sorted it in 369.
10:27And I have sorted it in 258.
10:31Now my job is to merge.
10:35What will I do in merge?
10:38I will make a temporary array.
10:41I can name this temporary array.
10:44I will make a temporary array.
10:45I will make the same size.
10:46In which I have left elements and right elements.
10:50What will I do in size?
10:52This will be left elements plus right elements.
10:56The total number of left elements plus right elements.
10:59The total combined size will come.
11:01This will be my temporary array.
11:03Now in the temporary array,
11:05I can say that I have 6 elements of space.
11:09Now I know that my left part is sorted.
11:12And my right part is sorted.
11:15I will merge this sorted array.
11:18I will make a big sorted array.
11:19What will I do in that?
11:21I will take two iterators.
11:23The first iterator will go to 369.
11:26Here I will write 369.
11:28The second iterator will go to 258.
11:31I have taken an index which will track this small part.
11:34And one index which will track this big part.
11:37What can I say?
11:37Because this is sorted.
11:39And this is sorted.
11:40So it will be the smallest elements.
11:43So if I compare these two.
11:46I will place the smallest element.
11:48I will place the smallest element in the first index.
11:50Then I will have a third iterator.
11:52What will I do?
11:53I will track this.
11:55Now my 0th index is empty.
11:58What will I do?
11:59I will compare these two.
12:00The first part is sorted.
12:03The first part is sorted.
12:03So compare them to the first part.
12:04I will compare them.
12:05When I compare them to 3 and 2,
12:07I realized that 3 and 2 are small.
12:10So I will store them in the temporary array.
12:13And I will increase the index here.
12:16And what will I do?
12:17I will store them here.
12:18So my index will come here.
12:21Now I will compare them to the left part.
12:23Or the right part is small.
12:25Obviously my left part is small.
12:27So what will I do?
12:29I will write 3 here.
12:31I will increase the index here.
12:32I will increase the index.
12:35I will increase the index here.
12:37Now I will compare them to the left part.
12:39So I will compare them to the left part.
12:39And the right part is small.
12:40Obviously the right part is small.
12:42Then I will write 5.
12:45Now I will increase the index here.
12:48I will increase this index.
12:51Now I have to compare that my left part is small or my right part is small.
12:56Obviously my left part is small.
12:58So what will I do?
13:00I will write this 6 in my temporary area and increase this index.
13:05Now I will compare this index.
13:08Now I will compare if my 9 is small or 8 is small.
13:11Obviously 8 is small.
13:12So I will take 8 here.
13:13I will take the small element first so that our final temporary elements will be sorted in ascending order.
13:22So I will take 8 here.
13:24I will increase the index.
13:26After that 8 is completely removed from here.
13:29And my second part will be finished.
13:32Now what is left in my right part?
13:33My right part is my 9.
13:36So what will I do?
13:37I will take this 9 in the last area.
13:40So I have made a temporary area.
13:42And what did I do?
13:44My left sorted part and my right sorted part.
13:47I will compare them both.
13:49The small element I have arranged one after one after one after one after.
13:53And the final answer you will notice.
13:56I have a sorted array in ascending order.
13:58How is sorted array?
14:00I have not sorted directly.
14:02I have divided in small parts.
14:04I have solved the small parts.
14:06Then I have merged the solved parts.
14:09This is called my merge step.
14:11I have merged the solved parts.
14:14I have merged the solved parts.
14:16I have merged the solved parts.
14:16First we divide and then we merge the solved parts.
14:19I have merged the left parts and right parts.
14:21Then we merge the small parts to form a bigger solution.
14:26Now I will summarize it a little bit.
14:28How will I summarize it?
14:30I will summarize it a little bit.
14:30Here my first array will see something like this.
14:34What can I say?
14:35My starting index will be 0.
14:37And my ending index will be equal to 5.
14:40Here I will remove my first mid.
14:42My mid will be equal to 2.
14:43So here I will perform the divide step.
14:47This will be my left division.
14:48This will be my right division.
14:50This will be my right division.
14:51In the left division, my starting index is 0.
14:53And for this array, my ending index will be equal to 2.
14:58What can I say?
14:58My ending index will be equal to mid.
15:01Why?
15:01Because the last element in this left array is my mid.
15:07So my ending index will be equal to mid.
15:10And here the starting index will be mid plus 1.
15:14Because this is the next element of mid.
15:16So here the starting index will be equal to 3.
15:20Which is also equal to mid plus 1.
15:22And here the ending index will be equal to 5.
15:25Now I have a small problem.
15:27But this problem is not too small.
15:29It will also be divided.
15:31So I will divide this problem.
15:33Here I will take my starting index is equal to 0.
15:36Here I will division.
15:37This will be my mid.
15:39And this will be my mid.
15:41This will be my mid plus 1.
15:43And this will be my ending index.
15:45In the same way,
15:46My starting index will be the starting index.
15:49This will be mid.
15:50This will be mid plus 1.
15:52And this will be my ending index.
15:54Now what will I divide in small parts?
15:57This is a single element.
15:58This is already sorted.
16:00So here I will hit my base case.
16:03This is my base case.
16:05This is also my base case.
16:06I can divide it further.
16:08This will be my starting index.
16:10This is my mid.
16:12This is my mid plus 1.
16:14This is my ending index.
16:15I will divide it further.
16:17So what will I do here?
16:19We will hit our base case.
16:21In the same way,
16:22I will divide it further.
16:22This will also be my base case.
16:25So this is my entire line.
16:26This is my base case.
16:28Now what do I do here?
16:30I divide it further.
16:33Now I will sort my problem and merge it.
16:37First, I will sort it.
16:39How do we sort it?
16:39How do we sort it?
16:39To combine these two parts,
16:41I need a temporary array.
16:43So I have made a temporary array.
16:45I will make a temporary array.
16:46I will compare them to 6 and 3.
16:50Obviously 3 small.
16:51I will write it further.
16:52Then I will write the left part.
16:54Then I will write it further.
16:55The sorted sequence is in a temporary array.
16:58I will copy this array.
17:00Where will I copy it?
17:02In my original array.
17:03I will copy it later.
17:03In the original array,
17:04I will copy it further.
17:06In the same way,
17:07if I have 3 or 6,
17:09I have 9.
17:10How do I combine them?
17:11How do I merge them?
17:12I will create a temporary array.
17:14It will be 3.
17:16I will put in 3 parts.
17:17First, 3 and 9.
17:21Then 6 and 9.
17:22Then 6 and 9.
17:25Now this is my temporary array.
17:27I will copy it in the original array.
17:29Then there will be sorted sequence.
17:32The same thing is merged.
17:33We will do it here.
17:35Then we merge the final array.
17:38This will be sorted array of my original array.
17:42Now let's clear 3 things in the original array.
17:44First, what will be my base case?
17:46My base case will be that.
17:48When I start my starting array of my original unsorted array.
17:48My starting index will be greater than my ending index.
17:51Or equal to it.
17:53When the ending index is equal,
17:55I have a single element.
17:57When I talk about this case,
17:59then my starting index is equal to my ending index.
18:02I will not do any work in this case.
18:03If my starting index is greater than my ending index,
18:06then this is an invalid case.
18:08In this case, I will not do any work in this case.
18:10Let's discuss what I have done in my recursion.
18:12What is the work done in this case?
18:13What is the work done in my recursion?
18:15I have divided my arrays.
18:16After dividing them,
18:17I have called them to merge the same function.
18:21This is my inner function call.
18:23The third work is discussed here.
18:24I will sort the left part.
18:26Then I will sort the right part.
18:28Then I will merge my parts.
18:31Then I will merge my recursion.
18:32So I will work in recursion.
18:34When will I call the inner function call?
18:37I have called the inner function here.
18:39I have called the merge sort function.
18:42Then I will solve the left part.
18:45Then I will solve the right part.
18:47Then I will solve the same question.
18:49What should we do?
18:50We will solve the same question.
18:51We will solve the same problem.
18:53We will solve the problem and solve the problem.
18:54It will be better in our solution.
18:56well.