[0:00]Now, we have seen what is merging and also we have seen how multiple lists can be merged together that is in two-way merging or M-way merging we have seen.
[0:14]And if there are multiple list, then we can merge them in different patterns, we have seen that.
[0:20]Now let us see merge sort, that is a recursive procedure.
[0:26]And this is divide and conquer procedure.
[0:30]The divide and conquer strategy says that if a problem is large then break the problem into sub problems and if the problem becomes small, then solve it and combine the solutions of the small problems or sub problems to get the solution for main problem.
[0:49]So here the problem is to sort these elements and we say that the list is very large.
[0:57]Then what is small? So basically if there is a single element, then we say it's small.
[1:03]So single element means we don't have to sort it. So yes, in merge sort, we say if there is just a single element, then we don't have to sort this.
[1:10]Otherwise, if there are two elements also, we have to call it as a bigger problem or large problem.
[1:18]If there's a single element, then we say it's a small problem.
[1:23]Merge sort follows divide and conquer, therefore, it's a recursive algorithm.
[1:30]Let me write the algorithm. Let me write the algorithm, then I will trace the algorithm.
[1:37]Let us see, algorithm merge sort, what are the parameters it takes?
[1:50]It takes two parameters, that is beginning of a list and ending of a list, so low and high.
[2:06]Then we check if low is less than high.
[2:11]Means, if low is equal to high, it means there is a single element.
[2:16]Low is less than high means at least there are two elements, so list is large.
[2:20]If low is less than high, then we will find out mid, that is low plus high by 2.
[2:30]What for are we finding mid? Like if I find 1+8/2, that is 9/2, I get 4, so this will be mid.
[2:39]What for? We say that this problem is large, so we break it into two sub-problems.
[2:46]That's what we find mid. Then what to do with the left-hand side?
[2:50]Perform merge sort recursively. Perform merge sort on the right-hand side recursively. So perform mid, find out mid, and perform merge sort from low to mid, and also perform merge sort from mid + 1 to high.
[3:16]So by performing merge sort on the left-hand side, we will sort this one and we sort the right-hand side. So when two lists are sorted, we are breaking this into two lists, and when two are sorted, we can merge them together.
[3:30]So perform merge from where? Low to mid is one list, and mid + 1 to high. So we pass three parameters. So that's all. This is a simple algorithm for merge sort. This is divide and conquer.
[3:47]How merging is done? We have already seen the procedure how merging is done.
[3:52]But the point here is when the single array is given for sorting, we are breaking into two sub-arrays, and we are saying there is one first list and that is second list.
[4:06]So single array will be containing two lists, and we have to merge them.
[4:16]Let us see how it works. Let us see the tracing.
[4:20]Now based on this algorithm only I will do tracing. Initially we'll be passing low as one and high as eight, so let us take for these set of elements. So first time we pass one and eight.
[4:33]It will find out mid, and it will divide the list, and this side, that side. So mid is perform and perform merge sort from low to mid. That is from 1 to 4.
[4:47]It will go this side. And it has to go on the right-hand side also, but not now. It will go afterwards.
[4:54]But I will draw this one also. So let us take this one. So it will call itself from 5 to 8 on the right-hand side.
[5:01]So it has broken them into two lists, first part and the second part.
[5:05]And then afterwards merge. So first of all, let us finish this and this.
[5:11]Now merge sort calls itself. Low is less than high. Yes, 1 is less than 4.
[5:19]So again, find out mid, and call these two. So it means this four elements are also large, divide them.
[5:27]So this side 1 to 2, and this side 3 to 4.
[5:36]Now when we take this, again low is less than high. Yes, there are two elements, so this is still large.
[5:43]Again split it. So 1 to 1 on this side, and 2 to 2 on this side.
[5:54]Now there are just one-one elements. See if you have seen previous video, you may know how do a merge works, two-way merge sort works.
[6:05]See if you have seen previous video, you know how two-way merge sort works.
[6:10]Now here also merge sort is working in a similar way. One, one array was given, so it has splitted and then splitted, then splitted. Now it has reached one-one element.
[6:21]Now one element is there, means it's a single list with one element.
[6:26]Now these two can be merged together. 3 and 9 are merged together. So the first merging is done for these two elements, and their result is obtained here. So this is the first merge done.
[6:39]This is the first merge done. It will merge these two elements.
[6:44]So 3 and 9 are merged. Then coming to this side, it will split them and get 3, 3 on this side, and 4, 4 on this side.
[6:57]Then it will merge the elements. 3 and 4 are merged.
[7:01]So first 9 and 3 were merged. So the result was 3, 9. And now 5 and 7 and 5 are merged. Result is 5 and 7.
[7:15]This is combined. Now it will go back and perform merge here. So this is the third merge. So it will merge these two, so the result is 3, 5, 7, 9.
[7:30]Now this side is sorted. Actually, we have to sort this whole array.
[7:34]Break it and break it and break it. Now two elements, merge two elements, merge. Now merge these two also. So this side is sorted.
[7:44]Now same thing is done on the right-hand side also. 5 to 8 is there. So on that side it will divide this from 5 to 6, and that side it will be 7 to 8.
[7:56]And 5 to 6 will become 5, 5 and 6, 6.
[8:03]Now one-one element each. This is again splitted, one-one element. So these two are merged.
[8:09]So it becomes 4, 6. So this is the fourth merging.
[8:15]Then it will go this side. It will split again 7, 7 this side and 8, 8 this side. So it will split this also.
[8:25]Then again these two are merged. So it becomes 2, 8, one more list. So this is fifth merging.
[8:33]Now as these two are already sorted, it will merge these two. So it becomes 2, 4, 6, 8.
[8:40]So this is sixth merging. And then these two lists are merged to get a single list. That is 2, 3, 4, 5, 6, 7, 8, 9. This is single sorted list. That is seventh merge here.
[8:58]So this is how merge sort works.
[9:01]When a single array is given, recursively it will divide that array into smaller pieces until it reach one-one element, then it will start merging them.
[9:12]So you can see that eight elements were given, splitted, then splitted, then splitted. Now they are merged, merged, merged.
[9:21]So this is the working of merge sort.
[9:25]All right. So it's similar to two-way, but in two-way merge sort, we just take first two elements, the next two, the next two. But this is divide and conquer, and this is recursive.
[9:37]So it will simply divide and divide, and then that's how it reaches one-one element. Then it will start merging them.
[9:44]So what is different is only the pattern is changing, the approach, rest of the things are same.
[9:54]Right, result is sorted, and it is also merging two list at a time. So it is also two-way.
[9:59]But as it is recursive, we need some another name, so we call it as merge sort.
[10:05]Let us see the time taken by merge sort. So from the tree, the recursion tree, that is the tracing of that algorithm I have done.
[10:16]So I'll show you how the time is, how, I will show you how much time it takes.
[10:23]See, the merging has started in this level.
[10:27]This was just splitting. So how many elements are merged here? Two, two elements merge, two elements, two elements.
[10:33]Total how many elements? Eight elements are there. 2, 4, 6, 8. Eight elements are merged here.
[10:39]So I will say N elements are merged, all N elements. Then again merging is done at this level. So N elements are merged. Then again, eight elements are merged here.
[10:52]So N elements are merged each time. So total how many levels are there? 1, 2, 3, or 1, 2, 3. So total three levels are there. So for eight elements, I got three levels. It means it is log of 8, log of 8.
[11:09]1, and then 2, then 4. So when something is raising by two every time and is power of two lastly, power of two, that is 3 at the last, we are having one eight elements total. So 3 is log of 8.
[11:27]So how many passes are there? So actually these are not passes because it is recursive. First it will enter this side, then it will go that side. So it is not passes.
[11:36]Right, first it will finish left side, then right side. But levels if you see, so total how many levels? Log N levels are there. So this will be N. How many times? Log N times.
[11:49]So the time taken by merge sort is Theta of N log N.
[11:58]That's it. So the time for this one is also N log N.
[12:02]Now taking these numbers, I'll show you how this merge sort works. Low and high are taken. So example is 1 and 8.
[12:13]So let us see using the numbers, I'll show you. First of all, it will find out mid, and it will call merge sort on the left-hand side.
[12:20]So it will take these numbers and call 9, 3, 7, 5. Merge sort is called on this.
[12:30]Then now this is 1 to 4. Again, this becomes 1 to 4. So this is the first call, right? First call.
[12:43]Then 1 to 4. The first recursive call, 1 to 4 is 1 is less than 4. So again it will call itself by finding mid, it will call itself. So again it will split. So this is 9 and 3. So just 1 and 2.
[12:56]1 and 2. Then again, this is also low is less than high. This is low, and this is high. Just you can follow that one.
[13:06]Find out mid and split it. So 9 on this side, this is just 1, 1, and 3 on this side. This is 2, 2.
[13:17]Right, so it has called itself and itself and itself again. So this is one list it has splitted, then again this is splitted. Again this is splitted, and this side. Now these two are merged. So the result becomes what? 3, 9.
[13:34]Right, then it will go on the right-hand side. So this becomes 7, 5, that is 3, 4.
[13:41]Then it will come on the left-hand side. This is just 7, 3. Then it is just 5.
[13:49]So these two are merged. So it becomes 5 and 7.
[13:55]Second call has finished. Now this side is completed. This side is completed. So what is the next step? Merge. So these two are merged. So this becomes what? First 3, then 5, then 7, then 9.
[14:13]So that's how it has splitted, then splitted, then splitted, then merged. So till here it got the result.
[14:18]Now it will go on to the right-hand side. So this part, second part for this one. So this will be 6, 4, 8, 2, and this is from 5 to 8. This one.
[14:32]Now on this, sorry. 5 to 8. On this one, it is called 5 is less than 8. Yes, again find out mid, and call merge sort this one. So on the left-hand side it will be called.
[14:43]So this will become 6, 4. It will be 5, 6. Indices are 5, 6. Then on this, again merge sort is called. So 5 is less than 6. So again find mid, and call merge sort.
[14:56]So it will become 6, and this is index 5. Now low is also 6, high is also 6. It will go on the right-hand side, this call.
[15:07]For this one, so this will be 4, and the index is 6. So low is also 6, high is also 6. Then merge. These two are merged. So it becomes 4 first, then 6.
[15:28]Then it will go on the right-hand side on this one. So right-hand side is 8 and 2. This is index 7 and 8. Now low is 7, high is 8. So low is less. Again, find out mid, and call this one.
[15:43]So this side it will be 8, and it will be 7. Now just one element. So go to the right side, 2 single element.
[15:57]Now merge. So left side completed, right side completed. Now merge. So 2, 8, it becomes 2, 8.
[16:05]Now this side, this side, both are sorted. Merge. Both are sorted, then merge. So this becomes 2, 4, 6, 8.
[16:19]So this becomes 2, 4, 6, 8. Now this is also sorted. This was already sorted beforehand, left-hand side it went. Now these two are merged together. 2, 3, 4, 5, 6, 7, 8, 9. So in this way, this list becomes 2, 3, 4, 5, 6, 7, 8, 9, sorted.
[16:44]This is how merge sort works. Tracing I have done.
[16:49]See earlier I have shown just indices, now in this I am showing numbers. And as it is calling itself two times, the tracing tree will be more like a binary tree. It will be like a binary tree.
[17:03]And if I say the traversal, then in which traversal merging is done? Post-order. First left, left, left, then right. Then root merge.
[17:16]Right, then right left, then right, then root merge, root merge. So merging is done in post-order traversal.
[17:27]That's it. So I have shown you tracing in two different ways. Now let us find out the time complexity of this algorithm by using recurrence relation.
[17:39]For this recursive algorithm, let us prepare recurrence relation and find out the time complexity of merge sort.
[17:47]If I say this algorithm takes T(n) time, then this is one condition, and this, if I ignore condition, and I say this is calculating mid, then it is calling itself. So T(n) of what? Half of the list, low to mid, half of the list, so n by 2. And again calling itself, so this is also n by 2. Then it is merging. Merging from where? Low to high. Two lists are there. Low to mid, mid + 1 to high. Two lists, total n elements. So merging takes n.
[18:22]So if I prepare recurrence relation by adding all these, ignore one there. Now this is T(n) is equals to two times T(n)/2 + n. So the recurrence relation is T(n) is equals to 2T(n)/2 + n when n is greater than 1.
[18:48]What it is doing when n is equals to 1? It's not doing anything. So we don't write 0. We can write 1 or some constant.
[18:57]Okay, some constant means 1, 10, anything you write. It's not doing anything, so better write 1. This is the recurrence relation. Now by using master's theorem, A value is how much? 2. B value is how much? 2. And f(n) is what? n.
[19:18]Now find out log A base B. So that is log 2 base 2 is 1. And power of n, k, it is 1. So this is log 2 base 2 is equal to k. They are equal.
[19:38]So we compare these two, and this is falling in case 2.
[19:44]Case 2. So case 2 says what? Whatever f(n) is, multiplied by log N. Write f(n) as it is and multiply it by log N. So I am using master theorem.
[19:56]Already this recurrence relation is solved in another video. You can look for that video.
[20:03]Right, it is in the second topic, that is divide and conquer. I have solved few recurrence relation. This you will find in the title of a video itself. Now here I directly I am using master's theorem. There's our videos on master theorem also.
[20:19]So time is Theta of N log N.
