Algorithms: Merge Sort

Views 406 546
80% 3 275 790

Learn the basics of merge sort. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell.

Science & Technology

Published on


Sep 27, 2016




Loading link...

Add to:

My playlist
Watch later
Comments 100
George Li
George Li 6 days ago
Thank you!
ali 21 day ago
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.
Vivek Singh
Vivek Singh Month ago
first time disappointed with your videos
Dharini Rajendran
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!
Chris DiGiuseppe
idk what you guys are complaining about, this wasn't that hard to follow.
Opeyemi Jonah
Opeyemi Jonah Month ago
I thought I was alone not understanding the steps.
torreyMama 2 months ago
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.
Manish Sharma
Manish Sharma 2 months ago
Thankyou so much !! You explained with such a simplicity....❤️
harsh shastri
harsh shastri 2 months ago
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
Jot Singh
Jot Singh 3 months ago
ekdum Fuddu code
Yrok Kory
Yrok Kory 3 months ago
Worst MS explanation on YT, beware
Hugo Ayala
Hugo Ayala 4 months ago
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
a K
a K 5 months ago
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!
Pavel Erokhin
Pavel Erokhin 5 months ago
EaswarD Sharma
EaswarD Sharma 5 months ago
Very nice! This made me clearer.
Zeo Huang
Zeo Huang 5 months ago
oh god, this mess my mind up so bad.......
N E M O 5 months ago
N E M O 5 months ago
Why Java is so scary?
Peterolen 5 months ago
Because it's a volcanic island?
Sandi Hadyono
Sandi Hadyono 6 months ago
What IDE u use??
Rhidlor 6 months ago
Please choose better variable names.
Abhilash Patel
Abhilash Patel 6 months ago
System.arraycopy is a SAST issue. Never use it in real application.
theobserver 6 months ago
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!
Parsa A
Parsa A 7 months ago
Why can't middle be defined as: (array.length)/2??
prateek s hiremath
prateek s hiremath 5 months ago
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).
Tyler Hansen
Tyler Hansen 7 months ago
Does this code not work for anyone else?
max 7 months ago
your voice is so annoying and the video is not helping it is showing
Zifu Song
Zifu Song 8 months ago
wow, I DONT follow
Suprise Nkosi
Suprise Nkosi 8 months ago
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.
Julio Gonzalez
Julio Gonzalez 9 months ago
Fergus Shan
Fergus Shan 9 months ago
0:01 Hi I'm Gayle LaakMcDowel -- did you skip a syllable there?
qwarlock Z
qwarlock Z 10 months ago
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.
intothelonelystreets 10 months ago
It is difficult to understand her words. She speaks too fast for a tutorial video.
videoguy640 11 months ago
Not a great explanation if you've never heard of it. But great as a refresher! Which is probably hackerRank intends it to be
Dan Russell
Dan Russell 11 months ago
I'm a senior engineer, and I didn't even understand this video's explanation of merge sort
Alan Saldívar
Alan Saldívar Month ago
Same here
Andersen Castañeda
I'm a classical pianist and I understood this explanation
Poul Julle
Poul Julle 3 months ago
@dijox i dont know what sort u work at, mergesort is not universally best, its about knowing your data, the structure and picking the right algo. and again, u dont implement merge sort to do a merge sort... u call a function. pleb
dijox 3 months ago
@Poul Julle I don't know what sort of companies you people work at, but merge sort is exactly the kind of algorithm you would need as a senior engineer.
Poul Julle
Poul Julle 3 months ago
@dijox lol, haters gonna hate. lets be real when did a senior last implement a merge sort? juniors are more likely to have done that recently and learning sorting algos
Jacob Gersfeld
Jacob Gersfeld 11 months ago
Really comprehensive- thanks! Have some big interviews coming up and trying to make sure I'm covered on all fronts.
Jacob Gersfeld
Jacob Gersfeld 2 months ago
@Mark Watson I'm a software developer now so at least one of them went well!
Mark Watson
Mark Watson 2 months ago
How did they go?
NimeniTv Year ago
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!
Ramanathan K
Ramanathan K Year ago
she takes the prize for the worst teacher in the history of computer science!
somekid Year ago
Oh bru, calm the hell down. She has various other videos out there that are fine.
Khayam Gondal
Khayam Gondal Year ago
Why not just use varible named start and end instread of leftStart and rightEnd? These makes it sound more complex.
Khayam Gondal
Khayam Gondal Year ago
I don't know how she makes simple things sound so complex and hard to understand.
Jonathan Doster
Splendid! Thank you.
Charles Maurice de Talleyrand-Périgord
Soothing keystrokes.
E Year ago
Okay J.K Rowling
Amr Idrees
Amr Idrees Year ago
I don't know what the comments are talking about .. I never knew merge sort before and I understood her explanation perfectly
The Gamegineers
when sortiing the two halves before merging, what is the best way to do it for large mix ups? a smaller merge sort? quick sort?
Dillon Smithson
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.
Afnan Shakeel
Afnan Shakeel Year ago
make it simpler
JP Year ago
Lol this isn't really an explanation, more of just. Hey, watch me code while I talk exactly what I'm typing.
Alan Saldívar
Alan Saldívar Month ago
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.
Jot Singh
Jot Singh 3 months ago
Zacree Carroll
Zacree Carroll 4 months ago
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.
Haliax 5 months ago
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.
Ali Faraz
Ali Faraz Year ago
fucking terrble
Integer factorisation(mistaken as merge sort) is all about the polynomial merger hierarchy of quick sort.
sunshinezz03 Year ago
Had it been a man explaining in this video, he would have not gotten so much flak from the viewers. Clearly, tells you what is wrong with the tech industry and why there are such less women in it. The number of misogynistic comments here are simply shocking.
Elhanan Elhanan
Please just take a breath before you complete your sentence, Please(:
Iskander Khabirov
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.
Alex Lazea
Alex Lazea Year ago
Good intention, bad output
RadioactivFly Year ago
You put curly braces on the same line as declarations. Blocked and reported.
Hentai Eyes
Hentai Eyes Year ago
This is why no one hires women
Adelin Ghanayem
If you know merge sort and just want to refresh your knowledge this video is perfect otherwise ... It is bad for newcomers
Eric SOM DUTT Year ago
Fuck her american accent.. horrible voice
Nishant Verma
Nishant Verma Year ago
Why do people usually prefer Java for such topics?
Pritish Mishra
It isn't bro. Different websites/universities use different languages or pseudocodes.
Dillon Smithson
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.
mrtrex01 Year ago
She doesn’t break this down well enough. She rushed through it and made you feel stupid on purpose. Bad teacher. This is coming from a person who knows merge sort.
Alan Saldívar
Alan Saldívar Month ago
@meow peow Yeah, her books are awesome, but her videos they are... just what they are lol.
Dan Yxng
Dan Yxng 5 months ago
meow peow well you did learn the basics of merge sort.
meow peow
meow peow Year ago
@Alessio Sangalli then it shouldnt have "Learn the basics of merge sort" in the description.
Alessio Sangalli
Yes this is intended for somebody that has already studied and now needs a quick refresh to go to an interview... Or did you think that hours of computer science college lessons could just be condensed in 9 minutes?
meow peow
meow peow Year ago
completely agree, same thing with every her lesson... at least her book "cracking coding interview" are not that bad
Sergio Torres
Sergio Torres 2 years ago
Hi, if anybody needs the source code here it is feel free to use it. github.com/oscargarza356/CodingProblems/blob/master/Solutions/MergeSort.java
Mario A
Mario A 2 years ago
This is why nobody reads books anymore. If only her teaching ability was as big as her ear.
Vengeanze 2 years ago
I am sharing my code because i feel like it is cleaner and doesn't use System.arraycopy package com.company; import java.util.Arrays; public class Main { static public void mergeSort ( int[] arr){ mergeSort(arr, new int[arr.length],0, arr.length); } static public void mergeSort ( int[] arr, int[] temp, int start, int end){ // [start, end) int length = end - start; if ( length > 1){ int middle = (start+end) /2; mergeSort(arr, temp,start, middle); mergeSort(arr, temp,middle, end); mergeArrays(arr, temp, start, end); } } static public void mergeArrays(int[] arr, int[] temp, int start, int end){ for ( int i = start; i temp[i] = arr[i]; } int middle = (start+end)/2; int index1 = start; int index2 = middle; for ( int i = start; i if ( index2 == end || (index1 arr[i] = temp[index1]; index1++; } else{ arr[i] = temp[index2]; index2++; } } } public static void main(String[] args) { // write your code here int[] arr = { 10, 2, 5, 7, 4, 9, 12, 1, 8, 6, 11, 3}; mergeSort(arr); System.out.println(Arrays.toString(arr)); } }
Dylan Maulucci
Dylan Maulucci 2 years ago
What are those arrows for import??
Shirin S
Shirin S 2 years ago
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 .
Saqib Saleem
Saqib Saleem 2 years ago
AGH!!! can't stand it anymore! I am giving you thumbs down! sorry
Saqib Saleem
Saqib Saleem 2 years ago
My God! thats annoying!!!
Saqib Saleem
Saqib Saleem 2 years ago
You, quite often, combine more than 3 words together while explaining and rush through them. What is that about?
hi friends please subscribe my you tube channel name: DIVVELA SRINIVASA RAO for videos on DAA(Design and Analysis of Algorithms)
Jin Izzraeel
Jin Izzraeel 2 years ago
arraycopy? Really?
rcgldr 2 years ago
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.
PLANET JIA - TECH 2 years ago
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
endale 2 years ago
This is too complicated to be considered a video on the "basics"
DyslexicAnaboko 2 years ago
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.
Michael East
Michael East 2 years ago
ok, I'll buy your book.
zhi gao Keng
zhi gao Keng 2 years ago
Very good!
choogiesaur 2 years ago
pls redo this vid with better conceptual explanation/clearer code! :) (like you had in quicksort vid)
baibhav ghimire
baibhav ghimire 2 years ago
This is how u explain if you memorize the whole code..
Suraj K
Suraj K 11 months ago
qwarlock Z
qwarlock Z 2 years ago
ruvid.net/video/video-TzeBrDU-JaY.html a nice other look at Merge Sort
Surya Sharma
Surya Sharma 2 years ago
If you didn't understand this, head to this video ruvid.net/video/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.
Sam Parsons
Sam Parsons 2 years ago
This is an ass explanation, everybody should pirate her book for shit like this.
Haroon Afridi
Haroon Afridi 2 years ago
many variables declarations in the code = fragile code
Haroon Afridi
Haroon Afridi 2 years ago
so many variables declarations.
Paulo Raoni
Paulo Raoni 2 years ago
I didn't like your explanation..
MrCabosco 2 years ago
Did anyone else notice that she didn't put the data in to the function but somehow got a compilation successful message?
Pritish Mishra
Was this supposed to be a joke?
Mengyi Chen
Mengyi Chen 2 years ago
may i know why the size should be plus 1 at the end of rightEnd-left start?
Faiz Quraishi
Faiz Quraishi 10 months ago
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
chun hei Lee
chun hei Lee 2 years ago
okay I think this is for advanced programmer :P
Nishchint Dhawan
Nishchint Dhawan 2 years ago
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.
Wislet Michel
Wislet Michel 2 years ago
Why Gale said the time complexity is always O(nlogn), isn't the worst case O(n*n)?
Akhil Gada
Akhil Gada 2 years ago
no because you always need to merge log n times. And for each merge it takes O(n).
Nishchint Dhawan
Nishchint Dhawan 2 years ago
Wislet Michel Average case and worst case both are O(n*logn)
Luis Rueda
Luis Rueda 2 years ago
I can tell you are reading from a script. Instead of using the word *copy you should have used the word *merge, since the algo is called merge sort. Also it is obvious you copy and pasted some elements. You are giving an unrealistic expectation that writing this from scratch is easy. I would have rather seen a more natural 'live' writing of this algo even if you had to struggle.
qwarlock Z
qwarlock Z 2 years ago
I love the idea. It is def intimidating when someone cranks out very clever code like this as if they did it on the first sweep. This is obviously something she has worked on and actually has solidly committed to memory. I am with you that I really learn more from people brave enough to raw code up in front of me. Having said that... I HATE coding in front of people and so understand why others do not do it.
Onufry Bonekip
Onufry Bonekip 2 years ago
Terrible explanation. The best part of the video is the first 5 seconds when you can see her pretty face and cute voice introducing herself. The rest, is very poorly explained merged sort and quite frankly, complete waste of time.
Toastbrot1000 2 years ago
your voice is so high pitched, its awful! But the content is quite good. Maybe you finde somebody who can synchronously speak your videos...
attsopal 2 years ago
very confusing.. cant keep up with her explanation ..
Sajad Ali
Sajad Ali 2 years ago
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!
qwarlock Z
qwarlock Z 2 years ago
qwarlock Z
qwarlock Z 2 years ago
ruvid.net/video/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.
Sajad Ali
Sajad Ali 2 years ago
qwarlock Z I will sir. Thanks.
qwarlock Z
qwarlock Z 2 years ago
Just look for a different explanation. There are so many ways to explain things . You will find one that makes it click.
Yevgeniy Vasilyev
Yevgeniy Vasilyev 2 years ago
Explanation is not good at all.
Sneha Kathare
Sneha Kathare 2 years ago
why don't u use simple code
qwarlock Z
qwarlock Z 2 years ago
There are def more simple explanations. This is not a good one as an intro to Merge Sort. This is more how to do a merge sort in a show off way to look good in the interview.
Sneha Kathare
Sneha Kathare 2 years ago
its too long code & difficult to understand
Chris Torok
Chris Torok 2 years ago
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.
Boxy Year ago
@David Dyer yes it is "Learn the basics of merge sort." (ps. sorry for late response)
David Dyer
David Dyer 2 years ago
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.
Karim Ihab
Karim Ihab 2 years ago
This code doesn't work
Michael 2 years ago
Terrible Lesson.
Omar Ch.
Omar Ch. 2 years ago
I can't follow your explaination
George Li
George Li 6 days ago
did you land a job in the end bro?
DyslexicAnaboko 2 years ago
+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.
Smart Mathimatics
Smart Mathimatics 2 years ago
Anyone send me video toturial about Edit Distance in DP ?
Next videos
Merge sort algorithm
Views 1 700 000
Merge Sort vs Quick Sort
Data Structures: Trees