Learn the basics of merge sort. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell. www.hackerrank.com/domains/tut...
This was great! Thought I'd add a note that helped me understand the algorithm better. This is a recursion problem, and in the video, we end the recursion when the "left end" is greater than the "right start." That's all well and good, but at a conceptual level, it's still a little unclear what the base case of the recursion is. To answer this question, consider that just before the "left end" is greater than the "right start" (i.e. in the second to last recursion), we are calling mergesort on a single-element array. But a single-element array is, by definition, already sorted! So basically we recurse until the solution is trivial ("this array is already sorted because it only has one element"), and then we start to combine all of our single-element arrays back into a larger, still-sorted array using mergeHalves.
@@notanonymous3976 you wanna see something cool? if you click on Amari Jefferson's channel and Kaison Tony's channel you can see that they both joined youtube on april 23, 2021... this clearly means that these are fake comments made by the same person to make you believe that this InstaPlekt bullshit is real lmao
This video shows top down merge sort. Note that merging does not begin until recursion reaches a point where two runs with a size of 1 element each is reached. Although top down merge sort is popular in educational environments, almost all implementations of merge sort used in libraries are variations of bottom up merge sort. For a basic bottom up merge sort, the repeated recursion used to divide an array is skipped and an array of n elements is considered to be n sorted runs of 1 element each , and the merging begins immediately, using iteration to maintain the indexes (or pointers) for the merge sort, as opposed to top down merge sort which has to push / pop indexes to / from the stack.
Merge sort worked out example: Unsorted array [8, 2, 7, 4, 9, 5, 6, 3] Sort left half [8, 2, 7, 4] [8, 2] [7, 4] [8] [2] [7] [4] [2, 8] [4, 7] [2, 4, 7, 8] Sort right half [9, 5, 6, 3] [9, 5] [6, 3] [9] [5] [6] [3] [5, 9] [3, 6] [3, 5, 6, 9] Merge the two halves [2, 4, 7, 8] [3, 5, 6, 9] [2, 3, 4, 5, 6, 7, 8, 9] The algorithm is very straight forward, implementation on the other hand could get a little tricky just remember that in order to sort the halves you'll need to call merge sort recursively on each half.
I think that in this specific simple problem we could just sort the whole list in one step, but in a more complex problem we would have to use Merge Sort Algorithm in order to solve the problem efficiently, as the whole purpose of Merge Sort is to break down the problem into two or more sub-problems until these are simple enough to solve directly.
dude its just fuking copy, the recrusion part was the real problem and she showed it to us. I hightly doubt that people came here cause they had a problem with copying the array ....
Jonas Grandt, she is just showing how merge-sort works towards the end she states that you'll never actually have to do this; other than C every other language as a nice library for search/sort and common data structures you can use.
+1 I feel that the variable names being used were a poor choice. Plus I can see in her book the code is different. I took the code from this example, wrote it down and now I am analyzing it while running it - but this explanation I felt was rushed and didn't explain much of anything.
@@DyslexicAnaboko I don't know why they do this if you're explaining something take extra minute which will help people understand the whole point of making the video smhhh
@@quirkyquester ha, sorry I didn't see this until now. Thanks for asking. No I did not and here is what I have to say about it. I interviewed twice, they botched my first interview (long story) and they asked me to interview again, so I did. I am unimpressed with how they conducted the interview process because everything hinges on you coding something in google docs while somehow simultaneously explaining what you are doing to the "interviewer". My first interviewer sounded like she didn't want to be conducting the interview and I am pretty sure that's a contribution to why it was botched and I interviewed again. At least they acknowledged that. You have 45 minutes to implement a crapshoot choice complexity of an algorithm. If you don't complete it in 45 minutes your interview is over. The irony is, I completed the code in my first interview under 45 minutes, the second question I could not complete in 45 minutes. As a test I did it again outside of the interview using the same rules and I was only able to do it in one hour and fifteen minutes. So in my opinion an interview like this is pointless (I have conducted well over 50 interviews myself) because they have taken all of my experience and expertise and tied it to an arbitrary coding exercise and put it in the dumpster because I couldn't finish it in under 45 minutes. I was told I was eligible to interview again in 9 months, I told my recruiter I would not interview with them again because this was a miserable experience and I don't like their interview process. Unless they change how they conduct their interviews and conduct a REAL interview I wouldn't bother with them again. I don't think what they are doing is really testing anything because in the real world I would never come up with a 45 minute or less solution and give it to anyone as a finished product. I think I would be a good fit there because I spoke to several Google engineers in person and after gauging their reactions and responses to the things I was saying I can tell the environment would be perfect for me. Their loss not mine. I like my current job and I am already an Architect with a possibility of becoming a director in the future. My thing is though, I don't want to be a manager, I just want to code and a place like Google facilitates that. That's the only reason I even cared to bother with the interview(s) because I didn't reach out to them, they reached out to me.
@@DyslexicAnaboko good job bro! I'm not planning to shoot for the FANG any more. The interview just isn't worth it. Thank you for sharing your experience!! Best of luck for you!
I think it would be more helpful to the viewer to point out to them that the actual sort itself happens in the merge method. I found this incredibly confusing as the mergesort method doesn't actually sort anything it is just the recursive driver breaking down the array into smaller parts.
You don't need extra variables like left or right. You could just use leftStart and rightStart in the while loop. This made it a bit confusing as the code was already long enough.
The only thing she's done different from the typical code for merge sort you'll find online is: she's used a temp array rather than removing elements from the two partitioned array and at the end checking which one's empty
Thanks for the explanation - sounds good but its' because I know it. But if I didn't I'd get it better if I've seen a break-down of the recursion on the pictures to see that divide& conquer gets these 'halves' to some small sizes in the end. I think also that you could have written the loop instead of using the System. method.. (and you could still mention that the library could be used). Why there are '+1' in 'size' and copy of the rest ?
If you are a newbie to mergesort please come later - learn its basics and practice first. If you still couldnt get the code working after many hours of practice, come and watch this video. Its beautifully explained. Only after watching this, i can turn my pseudo code into working code. Thanks Gayle!
You can find better explanation of merge sort... She made it very terrible to understand for newbies... Before watching this read wiki and look other materials (if you are newbie as me) after that it will become more clearer.
Question: How is it that you "run the code" and it gives the output of a sorted array? you have no return values anywhere...? Im either blind or missing something here. The temp array needs to be returned somehow, but Im just not seeing it here.
By dividing the list of numbers to right half and left half gave me the impression of divide and conquer, i feel like it would have been best if the analogy of sorting cards at hand was used.
First of all, the presenter is amazingly smart to write this code from scratch if not already scripted! Second, it is reinsuring to hear the part at 9:31 that in the real world it is not likely necessary to write sorting algorithms like this. Heap Sort seems to be the most fun to write.
@@JeanYvesLimantour like what playing guitar in ur dark basement oh look at me I'm a coding genius but I'm watching basic merge sort algorithm...get da fuk outta here
but when teacher said write steps which one is steps I mean how much of the numbers will be steps ? teacher give us some numbers and said just write the steps I mean this .
I don't know how but I always end up to understand your approach. You have a very good coding style, design. Thanks a lot. I honestly learned all the data structures through your videos. I can't thank you enough!
I completely agree. Being a good coder doesn't mean you are also a great teacher. Teaching complex and sophisticated subjects as sophistically isn't hard. What really hard is teaching it as minimal and understandable manner that anyone, literally anyone can understand.
She isn't teaching code if you do not know code you should learn a language before trying to learn about algorithms such as this. She is teaching algorithm through coding I could totally see how easily you could confuse the two but if you do not know a language this video is completely useless to you. I suggest learning a language before trying to learn how to implement recursive algorithms.
That's Gayle's style though. I usually watch her videos to get the possible solution, and then I jump to see the full detailed explanation from other sources.
@@alansaldivares Exactly and how awesome that we have both as a resource for free! I love the conceptual high level CS videos but the best way to solidify a concept for me is to both learn it's theory and then code it and get it to work on a real problem. She could have done some things to make this is a little cleaner also, however, maybe the abstract algorithm calls for specific void return type on the methods? IDK... I think overall it's a good explanation. I was able to take this and 'Kotlinize' it...and well it compiles so far just doesn't sort the array lol!! It will here shortly, I am close ...got it, I had an issue with the copy over portion :) Anyway good video and great point Alan!
1 2 3 4 5 6 7 8 9 10 Size 10 To calculate size using an expression Last index (10 in this case) - first index(1 in this case)+1 Which is 10 - 1 + 1 = 10 Similarly 0 1 2 3 4 5 6 7 8 9 Size 10 To calculate size using an expression Last index (9 in this case) - first index(0 in this case) + 1 Which is 9 - 0 + 1 = 10
I couldn't get it, may be I lack in my programming skills. But I really liked the explanation and, programming knowledge and efficiency of the lady. Amazing!
ruclips.net/video/vCAbbJgMsQk/видео.html Look at this one. It is much easier when you can watch the movement of the alog on a board. The basics is there are only three lines doing the work. She splits the array in half. So one lone takes the left half, one line takes the right half. then it sorts them and merges them. but because of recursion... it keeps splitting until there are LOTS of arrays but only of size 2. now it tests and swaps if it needs to. Then it starts merging them up and resorting. merge up resort.. up this tree. If it FAST because when it does its first merge it is only merging two little arrays of size two that are already sorted.. there are just a lot of them. then it just moves up the tree. That is how all the recursions work. Put off doing the work untill we have recursively split the problem into tiny units that can be done fast. Then put them back together. Hers is hard to see because she did not show in the explanation very much of how it worked. Also, hers is REALLY fast because she did a REALLY clever optimization that speeds it up but totally confuses the explanation. Her code in here is GREAT. It just sort of requires you already know how it works.
While yes, you could, its poor API design. Imagine the mergeHalves was being used by something that didn't calculate the middle point (like a unit test). You'd then be forcing the client to work out what the middle point is.
I would argue that if the methods are private then passing the middle index is fine. The client would be calling the initial Sort() method, so there isn't an opportunity for confusion.
A single array is being used for the whole sorting exercise here. For example, if the original array size is 8, after the first partition, the right half would have 4 elements and the left half would have 4.The length of the array is still 8 but the partitioned halves have 4 elements each and finding the middle element can only be done based on left and right indices for that sub array. Since this is recursive, the sub-arrays will go up to 1 element(base case).
Do technical interviews at FAANG companies in 2022 ever actually expect candidates to write mergeSort()? I'm fine with having it in my toolbox, just seems like something I'd never ever actually need not even in a coding interview. I'll assume I really actually will need it and obsess over it anyway. In a modern Java whiteboard problem, am I likely to be fine by just using Arrays.sort(myArray)? I guess not if the entire point of the question was to show I know the algorithm. Well, I'll quite my complaining and keep on studying it.
I'm running the same exact code in it's giving me "ArrayIndexOutOf BoundsException". where did we go wrong!? public class mergeSort { public static void mergesort(int[] array) { mergesort(array, new int[array.length],0,array.length-1); }
public static void mergesort(int[] array,int[] temp, int leftStart, int rightEnd) { if(leftStart < rightEnd) {
int middle= leftStart + (rightEnd - leftStart)/2; mergesort(array, temp, leftStart, middle); mergesort(array, temp, middle+1, rightEnd); mergeHalves(array, temp, leftStart, rightEnd); } } public static void mergeHalves (int[] array, int[] temp, int leftStart, int rightEnd) { int leftEnd=(rightEnd+ leftStart)/2; int rightStart = leftEnd +1; int size= rightEnd -leftStart +1;
int left= leftStart; int right = rightStart; int index = leftStart;
if you do (left+right)/2 it may potentially cause overflow, which will be a negative point in the real interview. The correct way is left + (right - left)/2. boo....
I don't agree with rest of the comments. The way she names her variables are amazing... I have been trying to understand mergesort for hours and this finally allowed me to get it!
My problem is that she goes through the material as if she's in a rush. She could've simply shown a non-coding way of doing a merge sort rather than spending 2/3 of the video coding the sort. Giving people the answer doesn't help them understand the concept. If you give people the pseduocode and help them understand what a Merge sort is actually doing, then they can go an implement that in code themselves.
Yes, it does. Although, I did find it a bit strange how she doesn't explicitly split the list into two parts before merging. However it still works the same way with int[] temp.
I think it's better to read the book and other sources first and then watch this video...I also advise watching it at 0.75 since she speaks really fast
I believe the concepts can be broken down better. I think mycodeschool does that. Gale's solution does work. But it is up to the learner to make a significant attempt to understand it. She's very similar to one of my CS professors who worked in industry. She moves quickly. Luckily there is a pause and rewind button. It is REALLY important for those of use to visualize this somehow. But once you learn it, it's hard to unlearn it as long as you visit it every once in awhile. It's also very important to at least attempt your own solution as well. There seems to be 100 ways to code something, but your mind only comes up with one.
This video is part of a series called Cracking The Coding Interview. A person who is learning merge sort for the first time is not the target audience.
Java is usually the language that is used to teach these topics in a University environment. You'll usually learn these in a data structures class, and they use Java because it is an easy language to teach a lot of the core elements behind Object-Oriented programming which can also be heavily used in implementing sorts and data structures.
I have to say I owe you an apology Gayle. I resented you for what the hiring industry has become, due to the HackerRank association... As if you started the ranking of developers in one completely odd discipline thus barring the door for us older cats who don't remember this stuff from college lol...I just kept thinking "Why should we waste so much time memorizing this crap? Isn't it enough to know they exist if we need them for a solution?" Well I was wrong...just in the last couple of weeks I dove headfirst down the rabbit hole(as is my thing) this time with Algorithms and a whole new world just smacked me in the face. I still resent the hiring practice. HackerRank should be about competitive programming not people's livelihoods, that being said, EVERY developer should learn and code up the foundational algorithms, learn time complexity and the by-product of these algorithms we call data structures. I knew about the main ones and what they did, thinking that was enough...10 years a developer without a rich study of this stuff...why??? I could have been great:(... lol j/k can still be! Sorry Gayle and thank you
If you didn't understand this, head to this video ruclips.net/video/4VqmGXwpLqc/видео.html for an explanation, then come back here. I think this would've been easier if the merge was explained in concept rather than in code.
See this is why I find pretty stupid asking people for algorithms and data structures during an interview. There is no way someone can come up with this solution out of the blue unless you have memorized the implementation of the merge sort. Yes you would have memorized this and other implementations. These are things that are already solved! I know it is important for candidates to be aware of performance and memory but that would be enough! If the candidates have a portfolio where they clearly demonstrate caring about performance and memory, that would be freaking enough!
there a lot of things remain unclear after watching this video. i would except a detailed explanations from a channel this size and from a company in the domain of teaching. the implemenation is also very confusing and could be written in more simplfied way. waste of 10 mins to be honset.
I still have no idea why she does not fix this. It is obviously really explained badly. Had she taken her time and did a standard merge sort and then optimized it this would have been great. But in its current form it is really useless.
public class MergeSort { public void sort(int[] arr) { mergeSort(arr, 0, arr.length-1, new int[arr.length]); } private void mergeSort(int[] arr, int left, int right, int[] temp) { if(left>=right) return; int middle = (left+right)/2; mergeSort(arr, left, middle, temp); mergeSort(arr, middle+1, right, temp); merge(arr, left, right, temp); } private void merge(int[] arr, int leftStart, int rightend, int[] temp) { int left = leftStart; int leftEnd = (leftStart+rightend)/2; int rightStart = leftEnd+1; int right = rightStart; int index=leftStart; int size = rightend-leftStart+1; while(left
Наука
This was great! Thought I'd add a note that helped me understand the algorithm better. This is a recursion problem, and in the video, we end the recursion when the "left end" is greater than the "right start." That's all well and good, but at a conceptual level, it's still a little unclear what the base case of the recursion is. To answer this question, consider that just before the "left end" is greater than the "right start" (i.e. in the second to last recursion), we are calling mergesort on a single-element array. But a single-element array is, by definition, already sorted! So basically we recurse until the solution is trivial ("this array is already sorted because it only has one element"), and then we start to combine all of our single-element arrays back into a larger, still-sorted array using mergeHalves.
If you know merge sort and just want to refresh your knowledge this video is perfect otherwise ... It is bad for newcomers
That's what I was thinking just typing away copy and copy that's all I hear
Agree
@Kaison Tony You're quite a trashy boyfriend and nobody cares.
@@notanonymous3976 you wanna see something cool? if you click on Amari Jefferson's channel and Kaison Tony's channel you can see that they both joined youtube on april 23, 2021... this clearly means that these are fake comments made by the same person to make you believe that this InstaPlekt bullshit is real lmao
I been coding for a long time and this video confuses the hell out of me.
For some reason, most of the algorithmic videos from HackerRank team are more confusing than helpful.
This video shows top down merge sort. Note that merging does not begin until recursion reaches a point where two runs with a size of 1 element each is reached. Although top down merge sort is popular in educational environments, almost all implementations of merge sort used in libraries are variations of bottom up merge sort. For a basic bottom up merge sort, the repeated recursion used to divide an array is skipped and an array of n elements is considered to be n sorted runs of 1 element each , and the merging begins immediately, using iteration to maintain the indexes (or pointers) for the merge sort, as opposed to top down merge sort which has to push / pop indexes to / from the stack.
Merge sort worked out example:
Unsorted array
[8, 2, 7, 4, 9, 5, 6, 3]
Sort left half
[8, 2, 7, 4]
[8, 2] [7, 4]
[8] [2] [7] [4]
[2, 8] [4, 7]
[2, 4, 7, 8]
Sort right half
[9, 5, 6, 3]
[9, 5] [6, 3]
[9] [5] [6] [3]
[5, 9] [3, 6]
[3, 5, 6, 9]
Merge the two halves
[2, 4, 7, 8] [3, 5, 6, 9]
[2, 3, 4, 5, 6, 7, 8, 9]
The algorithm is very straight forward, implementation on the other hand could get a little tricky just remember that in order to sort the halves you'll need to call merge sort recursively on each half.
Why not just use varible named start and end instread of leftStart and rightEnd? These makes it sound more complex.
...why don't we just Magic Sort the whole list???
Lol
I think that in this specific simple problem we could just sort the whole list in one step, but in a more complex problem we would have to use Merge Sort Algorithm in order to solve the problem efficiently, as the whole purpose of Merge Sort is to break down the problem into two or more sub-problems until these are simple enough to solve directly.
dude its just fuking copy, the recrusion part was the real problem and she showed it to us. I hightly doubt that people came here cause they had a problem with copying the array ....
Jonas Grandt, she is just showing how merge-sort works towards the end she states that you'll never actually have to do this; other than C every other language as a nice library for search/sort and common data structures you can use.
Except you still get these in interviews
I can't follow your explaination
+1 I feel that the variable names being used were a poor choice. Plus I can see in her book the code is different. I took the code from this example, wrote it down and now I am analyzing it while running it - but this explanation I felt was rushed and didn't explain much of anything.
did you land a job in the end bro?
@@DyslexicAnaboko I don't know why they do this if you're explaining something take extra minute which will help people understand the whole point of making the video smhhh
@@quirkyquester ha, sorry I didn't see this until now. Thanks for asking. No I did not and here is what I have to say about it. I interviewed twice, they botched my first interview (long story) and they asked me to interview again, so I did. I am unimpressed with how they conducted the interview process because everything hinges on you coding something in google docs while somehow simultaneously explaining what you are doing to the "interviewer". My first interviewer sounded like she didn't want to be conducting the interview and I am pretty sure that's a contribution to why it was botched and I interviewed again. At least they acknowledged that. You have 45 minutes to implement a crapshoot choice complexity of an algorithm. If you don't complete it in 45 minutes your interview is over. The irony is, I completed the code in my first interview under 45 minutes, the second question I could not complete in 45 minutes. As a test I did it again outside of the interview using the same rules and I was only able to do it in one hour and fifteen minutes. So in my opinion an interview like this is pointless (I have conducted well over 50 interviews myself) because they have taken all of my experience and expertise and tied it to an arbitrary coding exercise and put it in the dumpster because I couldn't finish it in under 45 minutes. I was told I was eligible to interview again in 9 months, I told my recruiter I would not interview with them again because this was a miserable experience and I don't like their interview process.
Unless they change how they conduct their interviews and conduct a REAL interview I wouldn't bother with them again. I don't think what they are doing is really testing anything because in the real world I would never come up with a 45 minute or less solution and give it to anyone as a finished product. I think I would be a good fit there because I spoke to several Google engineers in person and after gauging their reactions and responses to the things I was saying I can tell the environment would be perfect for me. Their loss not mine. I like my current job and I am already an Architect with a possibility of becoming a director in the future. My thing is though, I don't want to be a manager, I just want to code and a place like Google facilitates that. That's the only reason I even cared to bother with the interview(s) because I didn't reach out to them, they reached out to me.
@@DyslexicAnaboko good job bro! I'm not planning to shoot for the FANG any more. The interview just isn't worth it. Thank you for sharing your experience!! Best of luck for you!
I think it would be more helpful to the viewer to point out to them that the actual sort itself happens in the merge method. I found this incredibly confusing as the mergesort method doesn't actually sort anything it is just the recursive driver breaking down the array into smaller parts.
Thanks bro been confused for hours wondering why the mergesort doesn't sort anything!!
I'm a senior engineer, and I didn't even understand this video's explanation of merge sort
This just shows how bad the video was!
why even watching if u a senior bra..
Even i was thinking that i can write a code to work without sorting rather than sorting this way,with equal to less effort
Then you are not so a senior engineer? Joking, I don't understand either. Haha
@@PoulJulle-wb9iu cause we learn this in senior year bruh bruh
You don't need extra variables like left or right. You could just use leftStart and rightStart in the while loop. This made it a bit confusing as the code was already long enough.
She did it for readability!!!
The only thing she's done different from the typical code for merge sort you'll find online is: she's used a temp array rather than removing elements from the two partitioned array and at the end checking which one's empty
Thanks for the explanation - sounds good but its' because I know it. But if I didn't I'd get it better if I've seen a break-down of the recursion on the pictures to see that divide& conquer gets these 'halves' to some small sizes in the end.
I think also that you could have written the loop instead of using the System. method.. (and you could still mention that the library could be used). Why there are '+1' in 'size' and copy of the rest ?
If you are a newbie to mergesort please come later - learn its basics and practice first. If you still couldnt get the code working after many hours of practice, come and watch this video. Its beautifully explained. Only after watching this, i can turn my pseudo code into working code. Thanks Gayle!
You can find better explanation of merge sort... She made it very terrible to understand for newbies... Before watching this read wiki and look other materials (if you are newbie as me) after that it will become more clearer.
Question: How is it that you "run the code" and it gives the output of a sorted array? you have no return values anywhere...? Im either blind or missing something here. The temp array needs to be returned somehow, but Im just not seeing it here.
Integer factorisation(mistaken as merge sort) is all about the polynomial merger hierarchy of quick sort.
pls redo this vid with better conceptual explanation/clearer code! :) (like you had in quicksort vid)
Really comprehensive- thanks! Have some big interviews coming up and trying to make sure I'm covered on all fronts.
How did they go?
@@markuscwatson I'm a software developer now so at least one of them went well!
@@jiggyg123 congratulation!
This is definitely a great way to teach mergesort.
Very helpful, thank you so much for this video.
By dividing the list of numbers to right half and left half gave me the impression of divide and conquer, i feel like it would have been best if the analogy of sorting cards at hand was used.
First of all, the presenter is amazingly smart to write this code from scratch if not already scripted!
Second, it is reinsuring to hear the part at 9:31 that in the real world it is not likely necessary to write sorting algorithms like this. Heap Sort seems to be the most fun to write.
I'm surprised about the quantity of comments complaining about the video. It is great!
No it's not
@@schoudhury3463 ,have you considered other profession instead of coding? :)
@@JeanYvesLimantour like what playing guitar in ur dark basement oh look at me I'm a coding genius but I'm watching basic merge sort algorithm...get da fuk outta here
but when teacher said write steps which one is steps I mean how much of the numbers will be steps ? teacher give us some numbers and said just write the steps I mean this .
I don't know how but I always end up to understand your approach. You have a very good coding style, design. Thanks a lot. I honestly learned all the data structures through your videos. I can't thank you enough!
What's the use of temp here
Thanks for the Video! Watched it right bevor an exam and it really helped!
Lol this isn't really an explanation, more of just. Hey, watch me code while I talk exactly what I'm typing.
I completely agree. Being a good coder doesn't mean you are also a great teacher. Teaching complex and sophisticated subjects as sophistically isn't hard. What really hard is teaching it as minimal and understandable manner that anyone, literally anyone can understand.
She isn't teaching code if you do not know code you should learn a language before trying to learn about algorithms such as this. She is teaching algorithm through coding I could totally see how easily you could confuse the two but if you do not know a language this video is completely useless to you. I suggest learning a language before trying to learn how to implement recursive algorithms.
TRUE
That's Gayle's style though. I usually watch her videos to get the possible solution, and then I jump to see the full detailed explanation from other sources.
@@alansaldivares Exactly and how awesome that we have both as a resource for free!
I love the conceptual high level CS videos but the best way to solidify a concept for me is to both learn it's theory and then code it and get it to work on a real problem. She could have done some things to make this is a little cleaner also, however, maybe the abstract algorithm calls for specific void return type on the methods? IDK... I think overall it's a good explanation. I was able to take this and 'Kotlinize' it...and well it compiles so far just doesn't sort the array lol!! It will here shortly, I am close ...got it, I had an issue with the copy over portion :) Anyway good video and great point Alan!
may i know why the size should be plus 1 at the end of rightEnd-left start?
1 2 3 4 5 6 7 8 9 10
Size 10
To calculate size using an expression
Last index (10 in this case) - first index(1 in this case)+1
Which is
10 - 1 + 1 = 10
Similarly
0 1 2 3 4 5 6 7 8 9
Size 10
To calculate size using an expression
Last index (9 in this case) - first index(0 in this case) + 1
Which is
9 - 0 + 1 = 10
It's vert clear, thank you!
I couldn't get it, may be I lack in my programming skills. But I really liked the explanation and, programming knowledge and efficiency of the lady. Amazing!
Just look for a different explanation. There are so many ways to explain things . You will find one that makes it click.
qwarlock Z I will sir. Thanks.
ruclips.net/video/vCAbbJgMsQk/видео.html
Look at this one. It is much easier when you can watch the movement of the alog on a board. The basics is there are only three lines doing the work. She splits the array in half. So one lone takes the left half, one line takes the right half. then it sorts them and merges them. but because of recursion... it keeps splitting until there are LOTS of arrays but only of size 2. now it tests and swaps if it needs to. Then it starts merging them up and resorting. merge up resort.. up this tree. If it FAST because when it does its first merge it is only merging two little arrays of size two that are already sorted.. there are just a lot of them. then it just moves up the tree. That is how all the recursions work. Put off doing the work untill we have recursively split the problem into tiny units that can be done fast. Then put them back together.
Hers is hard to see because she did not show in the explanation very much of how it worked. Also, hers is REALLY fast because she did a REALLY clever optimization that speeds it up but totally confuses the explanation. Her code in here is GREAT. It just sort of requires you already know how it works.
ruclips.net/video/4VqmGXwpLqc/видео.html
Thanks a ton
this code has a flaw. on the 44th line change size to size + 1
Anyone send me video toturial about Edit Distance in DP ?
This was terrible. I don't get the part with the if (leftStart >= rightEnd), what does that mean?
array.sort()
Does this code not work for anyone else?
Thank you!
I don't get how anyone can think these things up in the first place, it's so counterintuitive. I need a new career
I've been watching these videos and they are kinda good. But one thing I feel like would be helpful is a better explanations of the why
Which editor it is ?
can't you just pass middle to mergeHalves rather than calculating it in both mergesort and mergeHalves ?
While yes, you could, its poor API design. Imagine the mergeHalves was being used by something that didn't calculate the middle point (like a unit test). You'd then be forcing the client to work out what the middle point is.
I would argue that if the methods are private then passing the middle index is fine. The client would be calling the initial Sort() method, so there isn't an opportunity for confusion.
Shouldn't we calculate the middle as : leftStart + (rightEnd - leftStart)/2 to avoid overflow as mentioned in BinarySearch video ?
Same question here.
And I still prefer (rightEnd + leftStart) >>> 1
Why can't middle be defined as: (array.length)/2??
A single array is being used for the whole sorting exercise here. For example, if the original array size is 8, after the first partition, the right half would have 4 elements and the left half would have 4.The length of the array is still 8 but the partitioned halves have 4 elements each and finding the middle element can only be done based on left and right indices for that sub array. Since this is recursive, the sub-arrays will go up to 1 element(base case).
lovely!
Every single coding tutorial ever has 10x as many words as needed. Reeeeeeee
Timsort: Hold my beer
Do technical interviews at FAANG companies in 2022 ever actually expect candidates to write mergeSort()? I'm fine with having it in my toolbox, just seems like something I'd never ever actually need not even in a coding interview. I'll assume I really actually will need it and obsess over it anyway.
In a modern Java whiteboard problem, am I likely to be fine by just using Arrays.sort(myArray)? I guess not if the entire point of the question was to show I know the algorithm. Well, I'll quite my complaining and keep on studying it.
I'm running the same exact code in it's giving me "ArrayIndexOutOf BoundsException". where did we go wrong!?
public class mergeSort {
public static void mergesort(int[] array) {
mergesort(array, new int[array.length],0,array.length-1);
}
public static void mergesort(int[] array,int[] temp, int leftStart, int rightEnd) {
if(leftStart < rightEnd) {
int middle= leftStart + (rightEnd - leftStart)/2;
mergesort(array, temp, leftStart, middle);
mergesort(array, temp, middle+1, rightEnd);
mergeHalves(array, temp, leftStart, rightEnd);
}
}
public static void mergeHalves (int[] array, int[] temp, int leftStart, int rightEnd) {
int leftEnd=(rightEnd+ leftStart)/2;
int rightStart = leftEnd +1;
int size= rightEnd -leftStart +1;
int left= leftStart;
int right = rightStart;
int index = leftStart;
while(left
second to last line is the out of bounds. should read array.length -1, however you must have figured it out by now :D
many variables declarations in the code = fragile code
Funny how Gayle seemed to have had a JavaScript moment around 3:40
if you do (left+right)/2 it may potentially cause overflow, which will be a negative point in the real interview. The correct way is left + (right - left)/2. boo....
What IDE u use??
@@kevinle5772 i dont understand
Very nice! This made me clearer.
Ur full of $hit
What are those arrows for import??
I don't know what the comments are talking about .. I never knew merge sort before and I understood her explanation perfectly
I don't agree with rest of the comments. The way she names her variables are amazing... I have been trying to understand mergesort for hours and this finally allowed me to get it!
side note but your keyboard is so satisfying should make an ASMR channel LOL (no but rly what keyboard is that)
It is a very good Video! Congratulations!
so many variables declarations.
She's just trying to show off hey look at me I know how to code
overload method should not be used here as it cause confusion
My problem is that she goes through the material as if she's in a rush. She could've simply shown a non-coding way of doing a merge sort rather than spending 2/3 of the video coding the sort. Giving people the answer doesn't help them understand the concept. If you give people the pseduocode and help them understand what a Merge sort is actually doing, then they can go an implement that in code themselves.
Why there are a lot of books back there with 4 kinds of language? The Chinese one is about interview lol.
all the books are about interview
very confusing.. cant keep up with her explanation ..
Does this Actually work?
Charaka Danansooriya not for me. Tried copying and pasting with no luck. Even found her information online with no luck
Yes, it does. Although, I did find it a bit strange how she doesn't explicitly split the list into two parts before merging. However it still works the same way with int[] temp.
no
it does works, here is the code github.com/oscargarza356/CodingProblems/blob/master/Solutions/MergeSort.java
I think it's better to read the book and other sources first and then watch this video...I also advise watching it at 0.75 since she speaks really fast
0:01 Hi I'm Gayle LaakMcDowel -- did you skip a syllable there?
Applying this to an algorithm I’m wanting to make
I believe the concepts can be broken down better. I think mycodeschool does that. Gale's solution does work. But it is up to the learner to make a significant attempt to understand it. She's very similar to one of my CS professors who worked in industry. She moves quickly. Luckily there is a pause and rewind button. It is REALLY important for those of use to visualize this somehow. But once you learn it, it's hard to unlearn it as long as you visit it every once in awhile.
It's also very important to at least attempt your own solution as well. There seems to be 100 ways to code something, but your mind only comes up with one.
This video is part of a series called Cracking The Coding Interview. A person who is learning merge sort for the first time is not the target audience.
I don't know how she makes simple things sound so complex and hard to understand.
You, quite often, combine more than 3 words together while explaining and rush through them. What is that about?
Please choose better variable names.
Why do people usually prefer Java for such topics?
Java is usually the language that is used to teach these topics in a University environment. You'll usually learn these in a data structures class, and they use Java because it is an easy language to teach a lot of the core elements behind Object-Oriented programming which can also be heavily used in implementing sorts and data structures.
It isn't bro. Different websites/universities use different languages or pseudocodes.
okay I think this is for advanced programmer :P
arraycopy? Really?
cool
Ha. Lines 13, 14. When Left more then right. If not we done! O nooooo.
I'm here after Leetcode gave us a a problem to sort a linked list in ascending order
ok, I'll buy your book.
It's trash just like her explanation
This is not the obvious way to explain or code the merge sort, a lot of extra stuff for nothing :(
Very good!
Splendid! Thank you.
I have to say I owe you an apology Gayle. I resented you for what the hiring industry has become, due to the HackerRank association... As if you started the ranking of developers in one completely odd discipline thus barring the door for us older cats who don't remember this stuff from college lol...I just kept thinking "Why should we waste so much time memorizing this crap? Isn't it enough to know they exist if we need them for a solution?"
Well I was wrong...just in the last couple of weeks I dove headfirst down the rabbit hole(as is my thing) this time with Algorithms and a whole new world just smacked me in the face.
I still resent the hiring practice. HackerRank should be about competitive programming not people's livelihoods, that being said, EVERY developer should learn and code up the foundational algorithms, learn time complexity and the by-product of these algorithms we call data structures. I knew about the main ones and what they did, thinking that was enough...10 years a developer without a rich study of this stuff...why??? I could have been great:(... lol j/k can still be! Sorry Gayle and thank you
If you didn't understand this, head to this video ruclips.net/video/4VqmGXwpLqc/видео.html for an explanation, then come back here.
I think this would've been easier if the merge was explained in concept rather than in code.
idk what you guys are complaining about, this wasn't that hard to follow.
See this is why I find pretty stupid asking people for algorithms and data structures during an interview. There is no way someone can come up with this solution out of the blue unless you have memorized the implementation of the merge sort. Yes you would have memorized this and other implementations. These are things that are already solved! I know it is important for candidates to be aware of performance and memory but that would be enough! If the candidates have a portfolio where they clearly demonstrate caring about performance and memory, that would be freaking enough!
there a lot of things remain unclear after watching this video.
i would except a detailed explanations from a channel this size and from a company in the domain of teaching.
the implemenation is also very confusing and could be written in more simplfied way.
waste of 10 mins to be honset.
vivkanand clg teaching
AGH!!! can't stand it anymore! I am giving you thumbs down! sorry
oh god, this mess my mind up so bad.......
Why Java is so scary?
I thought I was alone not understanding the steps.
you are awesome!
This code doesn't work
I like this clean code! Simple and easy to understand.
I still have no idea why she does not fix this. It is obviously really explained badly. Had she taken her time and did a standard merge sort and then optimized it this would have been great. But in its current form it is really useless.
you should use a picture while coding
public class MergeSort {
public void sort(int[] arr) {
mergeSort(arr, 0, arr.length-1, new int[arr.length]);
}
private void mergeSort(int[] arr, int left, int right, int[] temp) {
if(left>=right) return;
int middle = (left+right)/2;
mergeSort(arr, left, middle, temp);
mergeSort(arr, middle+1, right, temp);
merge(arr, left, right, temp);
}
private void merge(int[] arr, int leftStart, int rightend, int[] temp) {
int left = leftStart;
int leftEnd = (leftStart+rightend)/2;
int rightStart = leftEnd+1;
int right = rightStart;
int index=leftStart;
int size = rightend-leftStart+1;
while(left
I am not experienced enough to understand this. All i came here was for the first 20 seconds of the video