mergeSort(): A Graphical, Recursive, C++ Explanation

This video demonstrates a standard implementation of mergeSort() in C++, with graphics to help even the most novice of programmers understand how a recursive function, functions!
This video was produced at the University of Colorado Boulder for Data Structures CSCI 2270, taught by Rhonda Hoenigman.
merge() code: pastebin.com/bp...

[@burakbiyikli]

//This is an annotation of the code that they provide for merge.
void merge(int A[], int low, int high, int mid)
{
//We meed c[50] to put our sorted data into. This is as we need to maintain the order of A[] until the end of the function
//A[] is passed by reference as its an array (pointer), so in this application all merge() calls share A[].
// I & J are indexes for each half of the array section to be merged. In this function I & J will move right.
// k is the index to which we are writing to in the temporary array c[50]. (This merge will not work on array size > 50 lol.)
int i, j, k, c[50];
i = low;
k = low;
j = mid + 1;
//We have two sorted subsections in merge sort, so we need to determine which values to copy, take the example of:
// [0,2, 1,3] where each half of the array are independently sorted. here we can merge the array by looking at the beggining of each
// section and only reading the next value of a section if the last value read was lower. IE. read 0 and 1, 0 is lower so we write 0 to our result. r = [ 0 ? ? ? ?], then we read 2 and 1, 1 is lower so we write 1 and r = [ 0 1 ? ?], then we read 2,3 and 2 is lower so we write this to our result r = [0 1 2 ? ] then we have 3 left which this while loop doesn't handle, but the next does.
while (i

[@sidiousvic]

You're a fucking champ 🍻

[@sidiousvic]

One question though, this doesn't seem to work for uneven arrays. Why would that be?

[@burakbiyikli]

@@sidiousvic Sorry but I am not quite sure I follow what you mean by uneven. The main requirement of the code is that both regions given to merge are sorted. The code should run if you give it uneven arrays as I will explain, but in the execution of the algo. as shown it is called with typically even arrays as inputs.
Given this The function should work even if we feed it two sections containing [1,5] and [2,3,4,6,7,8,9] as the first loop terminates once c looks like [1,2,3,4,5] or so the second loop is skipped and the third loop moves the remainder such that c looks something like [1,2,3,4,5,6,7,8,9]
It has been a bit since i looked at it closely, but as the first loop does not really 'take turns' and the other two loops are for handling excess I believe the code should run on uneven sets. So the first loop runs until only one array is left then one of the remaining loops copies the rest from that array
The biggest Issue I have with this code is how it allocates memory that prevents it from sorting any set of a large size

[@raphaelramos4016]

I wish this comment achieve more likes than the video itself

[@tenzin8773]

I was scratching my head about how the recursive actually work for this algorithm. Now, it is clear. Thank you!

[@Daniel-sy5wz]

Thank you very much, two recursions in one function make me confused a while. This video is fantastic.

[@lipishah474]

Excellent interpretation of recursion with stack visualization.

[@stayALiVe143]

I generally don't comment on yt videos....
But i was struggling with understanding the recursive call since 3 hours , I stumbled upon this video...and Voila!
I tend to understand the visual representations much easier than other methods
This video was really great in taking me through process of understanding the call stack without rushing it
Such a great content ... Kudos to you for this!

[@DylanClarkSallee]

@@stayALiVe143 thank you very much! That means a lot. Glad a silly class project I did in college still brings value to people all these years later :)

[@gabrielumana5762]

I was struggling to do the merge part until I found your video and understood how to do it. Thanks a lot, really! And just keep coding :)

[@Albatross7770]

Best representation of call stack for merge sort. Much appreciated.....🙌🙌

[@lenzpaul2205]

Doesn’t explain how the merge function does the actual sorting ...

[@arslan113]

Yeah wtf

[@hufelix6091]

I already know how merge sort works, just forgot how to merge. I was watching this video and expecting he to explain merge() so honestly I was a little bit triggered when he just showed that "magic" gif.

[@mayur.a15]

This is video is only for mergeSort visualisation.

[@tarekshokry1366]

Great video, thank you very much ❤

[@dalvinder_kaur]

Thankyou very much. It helped me a lot.

[@gayanegrigoryan7779]

Thank you for the video! Its visualization really helps for better understanding of recursion.

[@walor-vo4yi]

amazing video man!!

[@czapla4]

This is one of the best tutorial videos I have ever seen - thanks to you I got to understand the recursion as well as the merge sort algorithm, so you killed two birds with one stone. Great work!

[@adritaanwar2279]

Thanks a lot! Finally understood how the recursion actually works!

[@Forlorade]

Great visualization, thank you, sir.

[@the_simone]

Thank you so much! This was really helpful!

[@danielmateofitness7618]

Front end trying to dive into back. This video helped.

[@aymenmejri8679]

Thank you very much ❤ ... Excellent interpretation.

[@omarfaruq1899]

wow good work.you visualize how recursive work.thank you

[@RandomNoob1124]

Lets just all appreciate how CONCISE this code is compared to other merge sorts.

[@rajshinde2840]

The video explanation is phenomenal just which call stack.

[@almogsharon5468]

Awesome tutorial!

[@suchitragiri4546]

thank you so much, it's helpful

[@ibrahimjamil3155]

this video should be on top because other are just explainging code and i wonder how htey even explain when they didnt understand as well so this video should be on top

[@shivammaniya2962]

thanks alot sir........ your learning is incredible 😍😍

[@thomasy314]

Smart and handsome?? Wow 😍 thank you!

[@DylanClarkSallee]

@@thomasy314 thanks bb 😘

[@angel4v369]

thanks for this video with stack. i get it !:)

[@sakibjobaid6667]

Thanks !!Great VIDEO.... It's really easy and helpful to understand how recursion works . Pls keep uploading like this>>>>>

[@piyushataware1968]

very helpful,thanks a lot!

[@artabinkabir2908]

What happen when you divide an array? Does it makes two different new arrays everytime with splitting elements? Does it mean we are assigning every splited to a new array?

[@tarekshokry1366]

Yes we divide each array into 2 different arrays

[@Int3rSys]

I am sorry but this is not called an explanation. It's a gentle introduction...

[@fefeisbored1958]

Why is this a gentle introduction and not an explanation?

[@shivanshsrivastava9279]

When the mergesort() on left statement returns then it should call mergesort on right part naa?
Why it calls merge() instead of mergesort() on remaining right part of array?

[@MunkyChunk]

This is great, thank you!

[@NineInchFailz]

Don't understand how that final two sub arrays suddenly get merged together sorted

[@dhanushanand5229]

can anyone explain why h is array size-1?

[@cosmology4168]

I am not understanding the recursive call.say when merge_sort(low,mid) is called until low ==high ,reaching a single element,
Then merge_sort(mid+1,high) is called and then mid+1 will be 1 like merge_sort(1,high) bcz from previous recursive func we get mid as 0.
And this where I am confused about how it does really execute.

[@rayalaananya8165]

i have the same doubt........can you please explain if the doubt is clarified by now?

[@Namesake..]

at the end of the first recursive call i.e., when low = 0, high = 1 and mid = 0, the function returns and the next mergesort for the second half is called. Remember at this point the values are low = 0, high=1 and mid =0 so the call would be mergesort(mid+1, high) = mergesort(1, 1) which would immediately return since 1 = 1.. and this follows.

[@keta063]

well done!!

[@sebastianfuentes1665]

muchas gracias y buena explicacion.

[@ektachanan7312]

i want to know ;how exactly does the merge method works?

[@shirins589]

sorry but how I find steps? when teacher said write the steps which line is step?? he gave the number of example

[@vedahanumanahallimath7516]

May i know how u did these graphics?

[@DylanClarkSallee]

PowerPoint! It’s a very accessible solution for things like this, but admittedly annoying to record over.

[@aishwaryaprabhu2119]

Can I please get the source code of the demonstration? I needed it for my college project

[@satyakighosh4226]

please give some codes to practice with and be smooth with it

[@Пятница-ю7ц]

how to run this code

[@kloud..]

Can you post the merge(A, low, high, mid) function code in the description? I want to see the logic for the merge function

[@DylanClarkSallee]

pastebin.com/bpiMpDxx

[@kloud..]

Ah thx

[@Isheel]

great work sir

[@pulkitchauhan6602]

good

[@nishitaaishwarya3624]

which tool did you use to create these graphics?

[@Marwan-oh4tk]

ty

[@logangraham2956]

interesting ...
even this person is saying "sort" as "sword"

[@MunkyChunk]

You need your ears checked mate.

[@manuelconte2127]

Your voice is like Mark zuckerberg xD

[@DylanClarkSallee]

That’s unfortunate

[@DAaaMan64]

lol "Just keep coding"
Will do.

[@benakbrako4857]

genant

[@ry9385]

This video is terrible