Algorithms: Merge Sort

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

[alix]

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.

[adelinghanayem]

If you know merge sort and just want to refresh your knowledge this video is perfect otherwise ... It is bad for newcomers

[rcgldr]

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.

[katerahul]

For some reason, most of the algorithmic videos from HackerRank team are more confusing than helpful.

[ferociousfeind]

...why don't we just Magic Sort the whole list???

[DyslexicAnaboko]

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.

[rubenalejandro]

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.

[KhayamGondal]

Why not just use varible named start and end instread of leftStart and rightEnd? These makes it sound more complex.

[forforma]

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 ?

[harshshastri]

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

[nishchintdhawan]

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.

[danrussell_official]

I'm a senior engineer, and I didn't even understand this video's explanation of merge sort

[Rdharini]

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!

[jiggyg]

Really comprehensive- thanks! Have some big interviews coming up and trying to make sure I'm covered on all fronts.

[choogiesaur]

pls redo this vid with better conceptual explanation/clearer code! :) (like you had in quicksort vid)

[mengyichen]

may i know why the size should be plus 1 at the end of rightEnd-left start?

[torreyMama]

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.

[raniketram]

Very helpful, thank you so much for this video.

[aaronrasing]

This is definitely a great way to teach mergesort.

[IskanderKhabirov_SE]

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.