for those who found time Complexity difficult to understand I think I can Help --> 1.Total no .of recursion calls = logN 2. No of numbers to merge in each recursion calls = N Time COmplexity =O(N*logN)
For those who are wondering about stability, the version of mergesort implemented in the video is unstable, but a simple tweak can make it stable changing the condition to first[i]
@@_DashingAdi_ suppose there are multiple same element/number in array, their positions will be preserved as it is.. without changing it... suppose [2(1st), 2(2nd), 2(3rd)] their positions will be preserved as it is...
Inplace merge sort is incorrect,he is still using extra array,how he can say this is inplace,if you don't know inplace sorting ,why you teach wrong concept?
I don't know how to explain this but when I am stuck on a uni task, I get a weird sensation of safety watching your videos as I know if I understand your video thoroughly, I will get the answer. Thanks.
Even after watching so many videos on merge sort i was in confusion, but this video alone did wonderful job to clear so many or all the doubts🤩, Thank you and keep going.
@Kunal Kushwaha In the sort in place code your base condition is if (end - start == 1). why is this the base I thought you wanted to return when you only have one element. but in your case you will have 2 elements because if end is 1 and start is 0 => 1-0 = 1 but that's 2 elements 0 and 1 so why is that base?
The key to understanding the reason is at the start of the code, where the function is called for the first time. There Kunal passed '0' as start and 'arr.length' ( 1 so the algo will proceed ahead to next call In the next call we will have arrays containing only a single element for example {2} Then start is 0, end is arr.length that is '1' , not '0'. Now, our array contains only 1 element and (end - start) will be (1 - 0) which is equal to 1!! Thus, the single element arr will be returned directly above !
The explanation is on the next level. I finished the second year of college of Technology and Informatics and those topics were hard and weird to me but now while i'm in vacation i decided to give it a second chance , to try to understand them finally because it's a really important topic. Thank you so much Kunal for your explanation and that all of this is free.
Hi Kunal, Thanks for uploading the video . Uploaded video are helpful and explanatory videos for fresher and experience folks. I have a suggestion for you. Please upload a video for Thread class ,Multithreading, thread pool etc..
I saw a dozen of merge sort videos but did not understand. Finally, your explanation went straight through my head and not a bouncer :) Thanks a lot for this amazing video !
Kunal is great but imo his explanation is spoon feeding I was not able to think on my own after his tutorials...Try Aditya verma videos after conpleting topics he helped me alot with thinking approach
At 29:15 you said there are N elements in the stack memory but there should be atmost logN elements in the stack memory as it is the height of the recursive tree......Btw thanks for this amazing DSA series it really helps me a lot
Merge sort by changing pointers of index value: import java.util.*; public class Main { public static void main(String[] args) { Scanner s=new Scanner(System.in); int arr[]={5,4,3,2,1}; merge(arr,0,arr.length); System.out.println(Arrays.toString(arr)); } public static void merge(int arr[],int s, int e){ if(e-s==1){ return; } int m=(s+e)/2; merge(arr,s,m); merge(arr,m,e); int ans[]=new int[e-s]; int i=0,j=s,k=m; while(j
My doubt is that the mid index is passed twice ( in left array, as well as in right array ), won't this repeat the number in the final array? I was wondering whether the right array's mid should be passed as mid+1 or something like that?? Anybody please clear my doubt!
Found it: Basically, when you copy the range of array, the last element is exclusive (i.e) when you pass Arrays.copyOfRange(arr, 0, mid); // mid is excluded! and when you pass Arrays.copyOfRange(arr, mid, arr.length) // mid gets included here, and arr.length = 5, so 5th index is excluded which doesn't exist as the index starts from 0, so last element is basically index 4, which is also covered !
Great video! I have one question: for the mergeInPlace function, it created a new array int[] mix = new int[e - s]; --> so is it still considered in place?
I like your videos bro but, the merge sort in place code is wrong, you do not use that extra array in merge function, it defeats the whole point of taking indices and stuff
I enjoyed this video. I just did not understand the part where mid turned out to be exclusive. so I did a mid+1, only half the sorted array is getting picked. If any one understands, kindly explain :)
All the things kunal explained was so much clear but I have a doubt about why is he using arr.length and not arr.length-1 in the in place merge sort part?
@@immortal4412 I know it's late, but in JAVA, arr.length returns total number of elements(1 indexed), not the SIZE of the array(0 indexed), unlike C++, example: {1,2,3,4,5} n = 5, but 5 is the 4th element.
Because the start varies for each recursion call. If we're in the last call the start can be somewhere like index->4 so if we use arr[l] the elements will get copied from 0 instead of the particular start index of that Recursion call. Using arr[l] will get the elements copied from 0 at all time regardless of which call hence it's wrong. When we use arr[s+l] we will copy the mix of that particular recursion call at the start of the array of that recursion call.
hey kunal i need your advice . im following your course and im loving it , but the thing is recently i was thinking of taking a coding ninja dsa + java course . read the reviews but cant make up my mind . i dont have much time left im already in 3rd year . please guide me would love to have advices and insights from everyone . thanking you in advance
@@blank2782 i dont know man i kinda in a dilemma , i just dont know what to do . for the past 3 years i have randomly scrolled and watched youtube . it was a havoc and now i just dont know what to do . and there is no time left
DSA + interview preparation playlist: ruclips.net/p/PL9gnSGHSqcnr_DxHsP7AW9ftq0AtAyYqJ
Only one request is... Please Do complete this playlist ( in whatever tym) just don't leave in between. It's the best course ever.
I will complete
@@KunalKushwaha when?
@@SunnyGupta00in October
@@vdas1335 not possible
dont worry nhi chhodega vo...he is lion 🦁 😅
for those who found time Complexity difficult to understand I think I can Help -->
1.Total no .of recursion calls = logN
2. No of numbers to merge in each recursion calls = N
Time COmplexity =O(N*logN)
Undoubtedly...best ever course for DSA on RUclips.
Thanks Kunal, for giving this level of content for free. ❤️
For those who are wondering about stability, the version of mergesort implemented in the video is unstable, but a simple tweak can make it stable
changing the condition to first[i]
What's a stable algorithm?
@@_DashingAdi_ suppose there are multiple same element/number in array, their positions will be preserved as it is.. without changing it...
suppose [2(1st), 2(2nd), 2(3rd)] their positions will be preserved as it is...
Probably you're the best teacher in my whole life that I am able to understand everything without asking much questions.
Simply you're the best
Best explanation than other RUclipsrs. Hope you will upload videos as like that will help us in competition programming.
Which language is he using ??
@@tasneemsf3421 Java
Inplace merge sort is incorrect,he is still using extra array,how he can say this is inplace,if you don't know inplace sorting ,why you teach wrong concept?
@@mdhaidarparwez968 exactly
It's the BEST course ever , i recommend everyone to watch it
I don't know how to explain this but when I am stuck on a uni task, I get a weird sensation of safety watching your videos as I know if I understand your video thoroughly, I will get the answer. Thanks.
Words are limited to appreciate this bootcamp!! Nice bro Thanks
Words are not enough to appreciate your way of teaching.
Exceptional,this guy deserves the best award for dsa
Thanks for teaching us like no one did till now!! One small request, please make lectures on dynamic programming as well!!
Even after watching so many videos on merge sort i was in confusion, but this video alone did wonderful job to clear so many or all the doubts🤩,
Thank you and keep going.
@Kunal Kushwaha In the sort in place code your base condition is if (end - start == 1). why is this the base I thought you wanted to return when you only have one element. but in your case you will have 2 elements because if end is 1 and start is 0 => 1-0 = 1 but that's 2 elements 0 and 1 so why is that base?
Yeah he made a mistake there. This code will fail for an array like [2, 1]
The key to understanding the reason is at the start of the code, where the function is called for the first time.
There Kunal passed '0' as start and 'arr.length' ( 1 so the algo will proceed ahead to next call
In the next call we will have arrays containing only a single element for example {2}
Then start is 0, end is arr.length that is '1' , not '0'.
Now, our array contains only 1 element and (end - start) will be (1 - 0) which is equal to 1!!
Thus, the single element arr will be returned directly above !
@@sufiserious798thanks a lot!
The explanation is on the next level. I finished the second year of college of Technology and Informatics and those topics were hard and weird to me but now while i'm in vacation i decided to give it a second chance , to try to understand them finally because it's a really important topic. Thank you so much Kunal for your explanation and that all of this is free.
Your vids are awesome man. This is exactly how algorithms should be taught. I've got my final interview with Microsoft tomorrow, wish me luck!
Best of luck!
were u able to crack it ?
@@sofiyarao815 I got 4/5 working solutions, unfortunately didn't get the job :(( but its all good practice!
@@youmadvids now whats your current status man
whats up?? where are you woking now?@@youmadvids
i wish i had your explanation skills you make it look so easy
best DSA course ever💯💯💯
Hi Kunal, Thanks for uploading the video .
Uploaded video are helpful and explanatory videos for fresher and experience folks.
I have a suggestion for you. Please upload a video for Thread class ,Multithreading, thread pool etc..
Kunal in every video -> recursively stating = Already explained in prev videos please watch ...
I saw a dozen of merge sort videos but did not understand. Finally, your explanation went straight through my head and not a bouncer :)
Thanks a lot for this amazing video !
Kunal is great but imo his explanation is spoon feeding I was not able to think on my own after his tutorials...Try Aditya verma videos after conpleting topics he helped me alot with thinking approach
@@rjesh2062 its not like spoon feeding. but we can say that his approach is addictive and even better than others.
The Best Explanation of MergeSort !
Kunal you are a gem man
Thanks for this video. Now I don't have any confusion in Recursion.
Please complete this series boss , it gives me panic once you give some gap in between 😄😬
At 29:15 you said there are N elements in the stack memory but there should be atmost
logN elements in the stack memory as it is the height of the recursive tree......Btw thanks for this amazing DSA series it really helps me a lot
O(log n): If you will declare the intermediate array in heap.
O(n): If your intermediate array is stored in stack.
Thank you brother ❤.... please complete the playlist
Kunal on Fire!
Merge sort by changing pointers of index value:
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int arr[]={5,4,3,2,1};
merge(arr,0,arr.length);
System.out.println(Arrays.toString(arr));
}
public static void merge(int arr[],int s, int e){
if(e-s==1){
return;
}
int m=(s+e)/2;
merge(arr,s,m);
merge(arr,m,e);
int ans[]=new int[e-s];
int i=0,j=s,k=m;
while(j
while copying the answer of mix in original array why do we have to take arr[i+s]?
37:45 There is Not arr,m,end this is arr,m+1,end
Recursion and how recursion worked lay hid in night; God said, "Let Kunal be", and there was light!
need to watch again it's already 11 at night and feels like overdose
forever grateful to you kunal!!!
Just a single word for you " Legendary " !!!!!!!
Kunal alpha character explanation I doesn't think anyone who can teach like him
Exceptional quality of teaching and content delivering.
Which one should we use if asked in an interview inplace or normal mergesort
first normal then inplace
@@KunalKushwaha thanks mate
Not gonna to Lie You are Really A King 👑
Not just like this dude You blew My mind
You are fantastic my Dude
You just made everything so Simple
My doubt is that the mid index is passed twice ( in left array, as well as in right array ), won't this repeat the number in the final array?
I was wondering whether the right array's mid should be passed as mid+1 or something like that?? Anybody please clear my doubt!
Found it: Basically, when you copy the range of array, the last element is exclusive (i.e) when you pass Arrays.copyOfRange(arr, 0, mid); // mid is excluded!
and when you pass Arrays.copyOfRange(arr, mid, arr.length) // mid gets included here, and arr.length = 5, so 5th index is excluded which doesn't exist as the index starts from 0, so last element is basically index 4, which is also covered !
can you explain these case with the inplace method@@jagadishrvjp4450
@@jagadishrvjp4450But even while using InPlace sorting (where he did not use .CopyOfRange) he still passed mid two times.
@@jagadishrvjp4450 Thanks man! Had the same doubt
Best explanation ever. Thank you
one of the finest in explaining things 👌
east and west,kunal is best
Debugging by my self helps me a lot 👌.
Hey Kunal, This is the best course I have came across. But I just wanted to ask you when will the course finish?
Very good and in depth explanation of the algorithm... Good Work 🙂
kunal bhaiya, when are you going to complete this series? i am desperately waiting for dp and graph videos..
Hey Kunal, you missed some conditions in merge sort code in function merge(), while(k < first.length + second.length -1 && i
everything is easy with ur explanation except the math part for me coz no clg need to learn calcu! great vid btw
Amazing Videos, I have been learning a lot from these! Please also explain Trees, Graphs & DP.
Eagerly wait for it kunal
I can say proudly that this is the best DSA course on youtube.
Thanks Kunal
Amazing lecture brother.
Hi Kunal pls also do the videos on applitude and reasoning it will help ful..
when e-s ==1 .. the array will be having 2 elements.. how that is working properly?
Love Babbar be like jldi jldi one shot recursion bna ke bacho ko geekforgeeks ke course bech deta hu 😂😂
Love babbar Only Makes us fool.
@@diveshkumar8025 definitely
haha
Your videos are amazing 👍
Thanks for this amazing explanation
I really like it 🤗❤🔥🔥👍🏻
Great video! Thank you very much Kunal!
hey kunal when u say "I am not going to teach u these easy stuff again" we actually get a recap of your previous concepts.
Hey kunal !!.. When ur going to complete entire lectures of DSA boot camp? Needed much : )
Brooo suppper👌👌👌👌👌👌👌
Coming here after watching your video on Recursion ( makes it so easy to understand ) 😂
Great explanation
Bro when will be this dsa playlist will be completed?
Great video! I have one question: for the mergeInPlace function, it created a new array int[] mix = new int[e - s]; --> so is it still considered in place?
long time, missed you.💗💗
Welcome back!
why do we use Sorting algorithms when we have a direct method which is Arrays.sort() 🙄 ?
lmao, .sort() also uses these methods. its not magic.
Video 30 Completed!
(17:40) I did not understand why you used the copyOfRange Method?
I like your videos bro but,
the merge sort in place code is wrong, you do not use that extra array in merge function, it defeats the whole point of taking indices and stuff
I've used the same program as of you of in-place algorithm, then why it's giving wrong answer ??
Because the algorithm is full of bugs
best sir in world
I enjoyed this video. I just did not understand the part where mid turned out to be exclusive. so I did a mid+1, only half the sorted array is getting picked. If any one understands, kindly explain :)
Hey Kunal, How your are using debugger in such a way that it is showing each and every step....is any extension installed or just using F5
still watching consistently
😀😀😀
😀😀
great video bro, thank you so much!!
This time complicated mergeSort into mix etc it should have been taught in simple method.
what if k=s in the in-place merge sort we dont even need the mix[] we can use arr[k]
thank youuu;)
All the things kunal explained was so much clear but I have a doubt about why is he using arr.length and not arr.length-1 in the in place merge sort part?
same.. have you figured it out?
@@immortal4412 I know it's late, but in JAVA, arr.length returns total number of elements(1 indexed), not the SIZE of the array(0 indexed), unlike C++, example: {1,2,3,4,5} n = 5, but 5 is the 4th element.
@@wegojim732 arrays are 0-indexed in C++ too, that is not the reason for using arr.length
first time kunal sir gets confused🤭🤫
Thank for the lecture. My support through subscribed already 😊
how tf every kunal is genius
Can you please complete the whole bootcamp.
Here your are using copyofrange method for java like same thing how to do in python?
arr[:mid] ,arr[mid:] use slicing
When copying elements of mix[ ] to our arr, why are we saying arr[s + l]? Can't we say arr[l] = mix[l]?
Because the start varies for each recursion call.
If we're in the last call the start can be somewhere like index->4 so if we use arr[l] the elements will get copied from 0 instead of the particular start index of that Recursion call.
Using arr[l] will get the elements copied from 0 at all time regardless of which call hence it's wrong.
When we use arr[s+l] we will copy the mix of that particular recursion call at the start of the array of that recursion call.
iterative code for merge sort - bottom up approach
static void iterativeMergeSort(int[] arr){
int sizeOfImgArr = 1;
for(sizeOfImgArr = 1; sizeOfImgArr
Number of comparison will not increase more then n- 1 ??
how is it going to be inplace mergeSort , if we are creating a new array in the mergeInPlace( ) method??
sir their is problem in printing the arrey in main class , because the syntex you give in github and the syntex in your video is different .
thankyou brother
Bro please complete the series
How after dividing arrays in halfs those halfs are getting sorted?
Same doubt dude😭
same same hahaha'
@@plutomessi21
we divide arrays until its size become 1.
when we merge both arrays of size 1 then it likes comparing two numbers.
what about comparisons made in copying of array in method "copyofrange"????
Thank You :)
42:36 broo plz clarify this part more
Why didn't you put 'return' while creating left and right arrays? There must be return when function has a datatype right?
because he saving the answer into keft or right variable arrays so instead of direct return you can save it in a variable
pretty cool stuff
hey kunal i need your advice . im following your course and im loving it , but the thing is recently i was thinking of taking a coding ninja dsa + java course . read the reviews but cant make up my mind . i dont have much time left im already in 3rd year .
please guide me
would love to have advices and insights from everyone .
thanking you in advance
Is this course not enough to crack interview
Kunal's course is enough bro, but if you still want to spend money on some course go ahead you will learn after that why this course is best. 😂
@@rishika9102 to be honest im in the 3rd video ,i just cant make my mind straight
@@blank2782 i dont know man i kinda in a dilemma , i just dont know what to do . for the past 3 years i have randomly scrolled and watched youtube . it was a havoc and now i just dont know what to do . and there is no time left
@@suvraneelsaha8973 ya that's the same for me ..